QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352430#6427. Just Another Game of StonesPorNPtreeWA 866ms76376kbC++143.6kb2024-03-13 11:05:422024-03-13 11:05:46

Judging History

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

  • [2024-03-13 11:05:46]
  • 评测
  • 测评结果:WA
  • 用时:866ms
  • 内存:76376kb
  • [2024-03-13 11:05:42]
  • 提交

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[k] & 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 (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: 3ms
memory: 75572kb

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: 866ms
memory: 76376kb

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
28979
92881
2495
627
9899
29441
6995
6189
16887
8329
21013
10547
48695
8431
32233
361
16523
12411
75407
8773
38387
28179
9837
46941
24643
11285
15993
5011
18423
47919
93471
19785
1357
3113
6937
12699
4623
17895
19869
55667
76027
27369
60745
83197
50853
86885
7639
50175
37955
...

result:

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