QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352415 | #6427. Just Another Game of Stones | PorNPtree | WA | 283ms | 76208kb | C++14 | 3.6kb | 2024-03-13 10:58:47 | 2024-03-13 10:58:48 |
Judging History
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'