QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352418#6427. Just Another Game of StonesPorNPtreeWA 0ms75444kbC++143.6kb2024-03-13 10:59:422024-03-13 10:59:43

Judging History

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

  • [2024-03-13 10:59:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:75444kb
  • [2024-03-13 10:59: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[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) {
            return;
            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: 0
Wrong Answer
time: 0ms
memory: 75444kb

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
1
1

result:

wrong answer 2nd numbers differ - expected: '0', found: '1'