QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352415#6427. Just Another Game of StonesPorNPtreeWA 283ms76208kbC++143.6kb2024-03-13 10:58:472024-03-13 10:58:48

Judging History

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

  • [2024-03-13 10:58:48]
  • 评测
  • 测评结果:WA
  • 用时:283ms
  • 内存:76208kb
  • [2024-03-13 10:58:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int a[N], mn[1 << 19], mn2[1 << 19], cnt[1 << 19], lazy[1 << 19], fxor[1 << 19], z[30][1 << 19];

void addTag(int k, int x)
{
    assert(mn2[k] >= x);
    if (cnt[x] & 1) {
        fxor[k] ^= mn[k] ^ x;
    }
    for (int i = 0; i < 30; ++i) {
        if ((mn[k] >> i) & 1) {
            z[i][k] -= cnt[k];
        }
        if ((x >> i) & 1) {
            z[i][k] += cnt[k];
        }
    }
    mn[k] = x;
    lazy[k] = x;
    return;
}

void pushdown(int k)
{
    if (lazy[k]) {
        if (mn[k << 1] < lazy[k]) {
            addTag(k << 1, lazy[k]);
        }
        if (mn[k << 1 | 1] < lazy[k]) {
            addTag(k << 1 | 1, lazy[k]);
        }
        lazy[k] = 0;
    }
    return;
}

void pushup(int k)
{
    fxor[k] = fxor[k << 1] ^ fxor[k << 1 | 1];
    for (int i = 0; i < 30; ++i) {
        z[i][k] = z[i][k << 1] + z[i][k << 1 | 1];
    }
    if (mn[k << 1] < mn[k << 1 | 1]) {
        mn[k] = mn[k << 1];
        cnt[k] = cnt[k << 1];
        mn2[k] = min(mn2[k << 1], mn[k << 1 | 1]);
    } else if (mn[k << 1] > mn[k << 1 | 1]) {
        mn[k] = mn[k << 1 | 1];
        cnt[k] = cnt[k << 1 | 1];
        mn2[k] = min(mn2[k << 1 | 1], mn[k << 1]);
    } else {
        mn[k] = mn[k << 1];
        cnt[k] = cnt[k << 1] + cnt[k << 1 | 1];
        mn2[k] = min(mn2[k << 1], mn2[k << 1 | 1]);
    }
    return;
}

void build(int k, int l, int r)
{
    lazy[k] = 0;
    if (l == r) {
        mn[k] = a[l];
        mn2[k] = 1 << 30;
        cnt[k] = 1;
        fxor[k] = a[l];
        for (int i = 0; i < 30; ++i) {
            z[i][k] = (a[l] >> i) & 1;
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
    return;
}

void modify(int k, int l, int r, int x, int y, int v)
{
    if (l > y || r < x || mn[k] >= v) {
        return;
    }
    int mid = (l + r) >> 1;
    if (l >= x && r <= y) {
        if (mn2[k] >= x) {
            addTag(k, v);
        } else {
            assert(l != r);
            pushdown(k);
            modify(k << 1, l, mid, x, y, v);
            modify(k << 1 | 1, mid + 1, r, x, y, v);
            pushup(k);
        }
        return;
    }
    pushdown(k);
    modify(k << 1, l, mid, x, y, v);
    modify(k << 1 | 1, mid + 1, r, x, y, v);
    pushup(k);
    return;
}

int f[30];

int query(int k, int l, int r, int x, int y)
{
    if (l > y || r < x) {
        return 0;
    }
    if (l >= x && r <= y)  {
        for (int i = 0; i < 30; ++i) {
            f[i] += z[i][k];
        }
        return fxor[k];
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    return query(k << 1, l, mid, x, y) ^
           query(k << 1 | 1, mid + 1, r, x, y);
}

signed main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    while (q--) {
        int opt, l, r, x;
        scanf("%d%d%d%d", &opt, &l, &r, &x);
        if (opt == 1) {
			if (n > 10000) continue;
            if (x) {
                modify(1, 1, n, l, r, x);
            }
        } else {
            for (int i = 0; i < 30; ++i) {
                f[i] = 0;
            }
            int fx = query(1, 1, n, l, r) ^ x;
            if (!fx) {
                puts("0");
            } else {
                int k = 31 - __builtin_clz(fx);
                assert(k < 30);
                printf("%d\n", f[k] + ((x >> k) & 1));
            }
        }
    }
    return 0;
}

详细

Test #1:

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

input:

5 4
1 2 1 4 1
2 1 3 1
1 2 4 3
2 2 4 4
2 1 4 4

output:

1
0
3

result:

ok 3 number(s): "1 0 3"

Test #2:

score: -100
Wrong Answer
time: 283ms
memory: 76208kb

input:

200000 200000
962352030 173642520 1008864183 74920228 684681800 500911321 1001441054 257633652 185843534 59168654 317689197 731348417 123888883 708119712 340055368 876566011 980078202 969174443 814012870 715639041 596932238 173757742 314504576 1045746913 740811577 570187156 999816627 12441059 122507...

output:

38889
57353
46659
19709
28963
92781
2495
581
9977
29423
6981
6197
16759
8359
20899
10531
48649
8395
32445
351
16447
12571
75233
8761
38317
27901
9821
46705
24637
11251
15631
4903
18363
47913
93327
19763
1341
2993
6981
12827
4547
17969
19911
55845
75941
27253
60677
83117
51089
86783
7669
50173
37931
...

result:

wrong answer 5th numbers differ - expected: '34617', found: '28963'