题目链接
题意
给你(n)堆石子，每堆有(a_i)堆石子，(q)次操作：
- 在([L,R])内有多少个子区间使得(Alice)(先手)在(Nim)博弈中获胜；
- 交换(a_{pos},a_{pos+1})的值。
思路
这题和cf617E差不多。
首先我们知道以下性质：
- (Nim)博弈只有当所有石子数异或为(0)才会导致先手必败；
- 在预处理前缀异或和后，交换相邻两堆石子的石子数只会影响(pos)处的值。
因此我们在预处理出前缀异或和后就可以用待修改莫队来解决本题，我们用(cnt)数组来处理出区间内(x)出现次数，(sum)表示区间内有多少个子区间异或和为(0)，那么最后答案为(frac{(R-L+1)(R-L)}{2}-sum)。
代码实现如下
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********
")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n, q, op, l, r, block;
LL sum;
int a[maxn], b[maxn];
LL cnt[1<<20+5];
struct que {
int l, r, id, t;
LL ans;
bool operator < (const que& x) const {
if((l - 1) / block != (x.l - 1) / block) {
return l < x.l;
}
if((r - 1) / block != (x.r - 1) / block) {
return r < x.r;
}
return t < x.t;
}
}ask[maxn];
struct modify {
int pre, val, pos;
}mfy[maxn];
void del(int x) {
--cnt[x];
sum -= cnt[x];
}
void add(int x) {
sum += cnt[x];
++cnt[x];
}
int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
while(~scanf("%d%d", &n, &q)) {
sum = 0;
for(int i = 0; i <= 1024 * 1024; ++i) cnt[i] = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = b[i-1] ^ a[i];
}
block = (int)pow(n, 2.0 / 3);
int nw = 0, idq = 0, idc = 0;
for(int i = 1; i <= q; ++i) {
scanf("%d", &op);
if(op == 1) {
idq++;
scanf("%d%d", &ask[idq].l, &ask[idq].r);
ask[idq].id = idq;
--ask[idq].l;
ask[idq].t = nw;
} else {
idc++;
++nw;
scanf("%d", &mfy[idc].pos);
int pos = mfy[idc].pos;
mfy[idc].pre = b[pos];
mfy[idc].val = b[pos+1] ^ a[pos];
b[pos] = b[pos+1] ^ a[pos];
swap(a[pos], a[pos+1]);
}
}
sort(ask + 1, ask + idq + 1);
int tmp = nw;
for(int i = 1, l = 1, r = 0; i <= idq; ++i) {
while (r < ask[i].r) add(b[++r]);
while (l > ask[i].l) add(b[--l]);
while (r > ask[i].r) del(b[r--]);
while (l < ask[i].l) del(b[l++]);
while (tmp < ask[i].t) {
tmp++;
if (mfy[tmp].pos >= ask[i].l && mfy[tmp].pos <= ask[i].r) {
del(mfy[tmp].pre);
add(mfy[tmp].val);
}
b[mfy[tmp].pos] = mfy[tmp].val;
}
while (tmp > ask[i].t) {
if (mfy[tmp].pos >= ask[i].l && mfy[tmp].pos <= ask[i].r) {
del(mfy[tmp].val);
add(mfy[tmp].pre);
}
b[mfy[tmp].pos] = mfy[tmp].pre;
tmp--;
}
ask[ask[i].id].ans = 1LL * (ask[i].r - ask[i].l) * (ask[i].r - ask[i].l + 1) / 2 - sum;
}
for(int i = 1; i <= idq; ++i) {
printf("%lld
", ask[i].ans);
}
}
return 0;
}