QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352418 | #6427. Just Another Game of Stones | PorNPtree | WA | 0ms | 75444kb | C++14 | 3.6kb | 2024-03-13 10:59:42 | 2024-03-13 10:59:43 |
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) {
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'