QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468729#8335. Fast Hash Transformreal_sigma_team#TL 4262ms184480kbC++237.6kb2024-07-08 23:48:462024-07-08 23:48:47

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 23:48:47]
  • 评测
  • 测评结果:TL
  • 用时:4262ms
  • 内存:184480kb
  • [2024-07-08 23:48:46]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

struct SqrtTreeItem {
    array<uint64_t, 64> arr;
    uint64_t xr = 0;

    SqrtTreeItem() {
        arr.fill(0);
        xr = 0;
    }
};

SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b) {
    SqrtTreeItem res;
    res.xr = b.xr;
    for (int i = 0; i < 64; ++i) {
        for (int j = 0; j < 64; ++j) {
            if (b.arr[i] >> j & 1) {
                res.xr ^= (a.xr >> j & 1) << i;
                res.arr[i] ^= a.arr[j];
            }
        }
    }
    return res;
}

inline int log2Up(int n) {
    int res = 0;
    while ((1 << res) < n) {
        res++;
    }
    return res;
}

class SqrtTree {
private:
    int n, lg, indexSz;
    vector<SqrtTreeItem> v;
    vector<int> clz, layers, onLayer;
    vector< vector<SqrtTreeItem> > pref, suf, between;

    inline void buildBlock(int layer, int l, int r) {
        pref[layer][l] = v[l];
        for (int i = l+1; i < r; i++) {
            pref[layer][i] = op(pref[layer][i-1], v[i]);
        }
        suf[layer][r-1] = v[r-1];
        for (int i = r-2; i >= l; i--) {
            suf[layer][i] = op(v[i], suf[layer][i+1]);
        }
    }

    inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
        int bSzLog = (layers[layer]+1) >> 1;
        int bCntLog = layers[layer] >> 1;
        int bSz = 1 << bSzLog;
        int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
        for (int i = 0; i < bCnt; i++) {
            SqrtTreeItem ans;
            for (int j = i; j < bCnt; j++) {
                SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
                ans = (i == j) ? add : op(ans, add);
                between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
            }
        }
    }

    inline void buildBetweenZero() {
        int bSzLog = (lg+1) >> 1;
        for (int i = 0; i < indexSz; i++) {
            v[n+i] = suf[0][i << bSzLog];
        }
        build(1, n, n + indexSz, (1 << lg) - n);
    }

    inline void updateBetweenZero(int bid) {
        int bSzLog = (lg+1) >> 1;
        v[n+bid] = suf[0][bid << bSzLog];
        update(1, n, n + indexSz, (1 << lg) - n, n+bid);
    }

    void build(int layer, int lBound, int rBound, int betweenOffs) {
        if (layer >= (int)layers.size()) {
            return;
        }
        int bSz = 1 << ((layers[layer]+1) >> 1);
        for (int l = lBound; l < rBound; l += bSz) {
            int r = min(l + bSz, rBound);
            buildBlock(layer, l, r);
            build(layer+1, l, r, betweenOffs);
        }
        if (layer == 0) {
            buildBetweenZero();
        } else {
            buildBetween(layer, lBound, rBound, betweenOffs);
        }
    }

    void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
        if (layer >= (int)layers.size()) {
            return;
        }
        int bSzLog = (layers[layer]+1) >> 1;
        int bSz = 1 << bSzLog;
        int blockIdx = (x - lBound) >> bSzLog;
        int l = lBound + (blockIdx << bSzLog);
        int r = min(l + bSz, rBound);
        buildBlock(layer, l, r);
        if (layer == 0) {
            updateBetweenZero(blockIdx);
        } else {
            buildBetween(layer, lBound, rBound, betweenOffs);
        }
        update(layer+1, l, r, betweenOffs, x);
    }

    inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
        if (l == r) {
            return v[l];
        }
        if (l + 1 == r) {
            return op(v[l], v[r]);
        }
        int layer = onLayer[clz[(l - base) ^ (r - base)]];
        int bSzLog = (layers[layer]+1) >> 1;
        int bCntLog = layers[layer] >> 1;
        int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
        int lBlock = ((l - lBound) >> bSzLog) + 1;
        int rBlock = ((r - lBound) >> bSzLog) - 1;
        SqrtTreeItem ans = suf[layer][l];
        if (lBlock <= rBlock) {
            SqrtTreeItem add = (layer == 0) ? (
                    query(n + lBlock, n + rBlock, (1 << lg) - n, n)
            ) : (
                                       between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
                               );
            ans = op(ans, add);
        }
        ans = op(ans, pref[layer][r]);
        return ans;
    }
public:
    inline SqrtTreeItem query(int l, int r) {
        return query(l, r, 0, 0);
    }

    inline void update(int x, const SqrtTreeItem &item) {
        v[x] = item;
        update(0, 0, n, 0, x);
    }

    SqrtTree(const vector<SqrtTreeItem>& a)
            : n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
        clz[0] = 0;
        for (int i = 1; i < (int)clz.size(); i++) {
            clz[i] = clz[i >> 1] + 1;
        }
        int tlg = lg;
        while (tlg > 1) {
            onLayer[tlg] = (int)layers.size();
            layers.push_back(tlg);
            tlg = (tlg+1) >> 1;
        }
        for (int i = lg-1; i >= 0; i--) {
            onLayer[i] = max(onLayer[i], onLayer[i+1]);
        }
        int betweenLayers = max(0, (int)layers.size() - 1);
        int bSzLog = (lg+1) >> 1;
        int bSz = 1 << bSzLog;
        indexSz = (n + bSz - 1) >> bSzLog;
        v.resize(n + indexSz);
        pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
        suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
        between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
        build(0, 0, n, 0);
    }
};


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q, c;
    cin >> n >> q >> c;
    vector<SqrtTreeItem> a(n);
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        vector<tuple<int, int, uint64_t>> res(m);
        for (auto& [s, o, A] : res) cin >> s >> o >> A;
        cin >> a[i].xr;
        for (int j = 0; j < 64; ++j) {
            for (auto [s, o, A] : res) {
                int k = j + s;
                if (k >= 64) k -= 64;
                if (o == 0 && (A >> k & 1)) a[i].xr ^= 1ull << k;
                else if (o == 1 && (~A >> k & 1)) {}
                else {
                    a[i].arr[k] ^= 1ull << j;
                }
            }
        }
    }
    SqrtTree tr(a);
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int l, r;
            uint64_t x;
            cin >> l >> r >> x;
            --l, --r;
            auto v = tr.query(l, r);
//            auto v = a[l];

            uint64_t res = v.xr;
            for (int j = 0; j < 64; ++j) {
                for (int k = 0; k < 64; ++k) {
                    if (v.arr[j] >> k & 1) {
                        res ^= (x >> k & 1) << j;
                    }
                }
            }
            cout << res << '\n';
        } else {
            int i;
            cin >> i;
            --i;
            a[i] = SqrtTreeItem();
            int m;
            cin >> m;
            vector<tuple<int, int, uint64_t>> res(m);
            for (auto& [s, o, A] : res) cin >> s >> o >> A;
            cin >> a[i].xr;
            for (int j = 0; j < 64; ++j) {
                for (auto [s, o, A] : res) {
                    int k = j + s;
                    if (k >= 64) k -= 64;
                    if (o == 0 && (A >> k & 1)) a[i].xr ^= 1ull << k;
                    else if (o == 1 && (~A >> k & 1)) {}
                    else {
                        a[i].arr[k] ^= 1ull << j;
                    }
                }
            }
            tr.update(i, a[i]);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3796kb

input:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

output:

64206
2023
31
1112

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

9 9 3
32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...

output:

9487331362121050549
3906661590723083106
15757672015979182109
4975471776251039345
11503109206538591140
3763610618439604410

result:

ok 6 tokens

Test #3:

score: 0
Accepted
time: 85ms
memory: 3624kb

input:

1 20000 400
32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...

output:

11827781865759498816
7454610526276185721
9581050724293785387
2177163806257271094
14004004964877510141
18073834598135159471
16966489063087641088
12289032565388413023
17823140805867698239
18104549908461644670
15570008264282957124
12400954982104000299
9842549278742638708
16535034933613060362
1561642006...

result:

ok 19600 tokens

Test #4:

score: 0
Accepted
time: 1928ms
memory: 7324kb

input:

500 20000 400
32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...

output:

9119093329811149961
16901643057538871933
17161855998497876349
3964234071281411558
13588188063229334268
15557968976322375381
4612345875926431452
9507168112801039022
9504318642653891468
217407202160767706
12982350345598971306
17957502630817476223
6353877977318728572
15552768639781831485
16778108770682...

result:

ok 19600 tokens

Test #5:

score: 0
Accepted
time: 3381ms
memory: 35676kb

input:

4000 20000 400
35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...

output:

11875257514484243925
3443357416933857062
16160011677622853538
1582145987019406393
15019762274690743371
3128972641411454448
10632018957963074870
2420532366876270818
16130728863118353230
15834956073901517645
18404809296474853851
10982435108266120760
16463778300806795274
11990886156320593058
1145171640...

result:

ok 19600 tokens

Test #6:

score: 0
Accepted
time: 4018ms
memory: 184048kb

input:

20000 20000 0
34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...

output:

8031710763259664674
10015579400510819759
9509776159199873854
252965904282343862
17471441301398284397
6167329408972068582
11581702001320217920
13373488743211628824
2094753313448112669
15503010008451014749
384500896248723935
10501371892025480221
8907735695899875922
14479597201387282763
164403466075406...

result:

ok 20000 tokens

Test #7:

score: 0
Accepted
time: 4262ms
memory: 184480kb

input:

20000 20000 20
28 31 1 17220760822712602145 12 1 10079395927654210001 40 0 10440736241216457314 20 1 14759495678166748212 55 1 8734257463550073646 60 0 543206106562221008 29 1 5402811237936853387 52 1 3884345269948184760 22 0 7873959847686200341 15 1 18396630536251250330 25 0 18230407003294263406 14...

output:

6531775129959975384
6212576544894999781
4191848452578359691
2769536540387251859
15526337103142577854
14948743844803225542
15235110724610778185
9004056994453026335
1028305510694260706
13496210650896843548
13961471020487846633
1864980030930734934
15243868808579626755
10451839696548403150
1178402342726...

result:

ok 19980 tokens

Test #8:

score: -100
Time Limit Exceeded

input:

20000 20000 400
41 15 1 10590708978689078436 33 0 17448869030270552656 37 1 16782453056389226553 2 1 18313039076194285622 53 1 7894371271572806769 60 1 14563226108042670650 56 0 12694119759311053234 12 1 969626878679760122 28 1 8906626075909573228 20 1 11632670066953088447 50 0 13097960756795495550 ...

output:

7425391644666486729
17533666397961516801
16986235811843827275
1784742314571007240
13192305384063626572
12739810377012216000
1179361465141596122
7698346401428161235
6903188112913915716
5380404381348976227
16126105607866972637
12798978320947566556
11234201442491665890
16073897288956866956
151328474491...

result: