QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468757#8335. Fast Hash Transformreal_sigma_team#WA 31ms390008kbC++177.0kb2024-07-09 00:19:442024-07-09 00:19:45

Judging History

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

  • [2024-07-09 00:19:45]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:390008kb
  • [2024-07-09 00:19:44]
  • 提交

answer

#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")

using namespace std;

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;
}
uint64_t go(const SqrtTreeItem& v, uint64_t x) {
    uint64_t res = v.xr;
    for (int i = 0; i < 64; ++i) {
        int c = __builtin_popcount(v.arr[i] & x) & 1;
        if (c) res ^= 1ull << i;
    }
    return res;
}

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

const int N = 4e4;
const int K = 6;

int n;
SqrtTreeItem v[N];
int clz[N], layers[N], onLayer[N];
int sz_layers = 0;
SqrtTreeItem pref[K][N], suf[K][N], between[K][N];
int lg, indexSz;

inline void buildBlock(int, int, int);
inline void buildBetween(int, int, int, int);
inline void buildBetweenZero();
inline void buildBetweenZero(int);
void build(int, int, int, int);
void update(int, int, int, int, int);


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 >= sz_layers) {
        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 >= sz_layers) {
        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;
}

inline SqrtTreeItem query(int l, int r) {
    return query(l, r, 0, 0);
}

inline void update(int x) {
    update(0, 0, n, 0, x);
}

void build() {
    lg = log2Up(n);
    clz[0] = 0;
    for (int i = 1; i < 1 << lg; i++) {
        clz[i] = clz[i >> 1] + 1;
    }
    int tlg = lg;
    while (tlg > 1) {
        onLayer[tlg] = sz_layers;
        layers[sz_layers++] = 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, sz_layers - 1);
    int bSzLog = (lg + 1) >> 1;
    int bSz = 1 << bSzLog;
    indexSz = (n + bSz - 1) >> bSzLog;
    build(0, 0, n, 0);
}


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

    int q, c;
    cin >> n >> q >> c;
    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 >> v[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)) v[i].xr ^= 1ull << k;
                else if (o == 1 && (~A >> k & 1)) {}
                else {
                    v[i].arr[k] ^= 1ull << j;
                }
            }
        }
    }
    build();
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int l, r;
            uint64_t x;
            cin >> l >> r >> x;
            --l, --r;
            auto v = query(l, r);
            cout << go(v, x) << '\n';
        } else {
            int i;
            cin >> i;
            --i;
            v[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 >> v[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)) v[i].xr ^= 1ull << k;
                    else if (o == 1 && (~A >> k & 1)) {}
                    else {
                        v[i].arr[k] ^= 1ull << j;
                    }
                }
            }
            update(i);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 27ms
memory: 390008kb

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: -100
Wrong Answer
time: 31ms
memory: 389952kb

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:

2251943714755008405
5320330399835658103
11444222880690360361
10236406355461836107
6701992379228958685
17580801933839203485

result:

wrong answer 1st words differ - expected: '9487331362121050549', found: '2251943714755008405'