带修莫队

• 允许离线的带区间修改的操作
  -将修改操作编号，称为"时间戳"

---

普通莫队是不能带修改的，我们可以强行让它可以修改

可以强行加上一维时间维, 表示这次操作的时间

• $[l-1,r,time]$
• $[l+1,r,time]$
• $[l,r-1,time]$
• $[l,r+1,time]$
• $[l,r,time-1]$
• $[l,r,time+1]$

排序

形如普通莫队

struct Node {int left;int right;int time;int id;friend bool operator <(const Node& a, const Node& b) {return belong[a.left] ^ belong[b.left] ? belong[a.left] < belong[b.left] ://先按左区间为第一关键字排序belong[a.right] ^ belong[b.right] ? belong[a.right] < belong[b.right] ://再按右区间为第二关键字排序a.time < b.time;//最后按时间排序}
}q[maxn];

复杂度

---

一般用的分块大小为$n^{\frac{2}{3}}$

可以用和普通莫队类似的方法排序转移，做到 $O(n^{\frac{5}{3}})$

这一次我们排序的方式是以 $n^{\frac{2}{3}}$为一块，分成了 $n^{\frac{1}{3}}$ 块

第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。

还是来证明一下时间复杂度（默认块大小为$n^{\frac{2}{3}}$）：

• 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是 $O(n)$
• 若左右端点所在块改变，时间一次最多会移动$n$个格子，时间复杂度 $O(n)$
• 左端点所在块一共有 $n^{\frac{1}{3}}$ 中，右端点也是` $n^{\frac{1}{3}}$种
• 一共 $n^{\frac{1}{3}}\times n^{\frac{1}{3}}=n^{\frac{2}{3}}$种，每种乘上移动的复杂度 $O(n) $，总复杂度 $O(n^{\frac{5}{3}})$

代码

Node

增加时间戳

int block, belong[maxn];
struct Node {int left;int right;int time;	//增加时间维int id;friend bool operator <(const Node& a, const Node& b) {return belong[a.left] ^ belong[b.left] ? belong[a.left] < belong[b.left] :belong[a.right] ^ belong[b.right] ? belong[a.right] < belong[b.right] :a.time < b.time;}
}q[maxn];

读入

一定要另开一个数组模拟改变的过程

for (int i = 1; i <= m; i++) {scanf("%s", p);if (p[0] == 'Q') {q[++cnt].left = read();q[cnt].right = read();q[cnt].id = cnt;q[cnt].time = t;}else {		//设b数组存改变后的值，存Modify里modify[++t].position = read();modify[t].now = read();modify[t].pre = b[modify[t].position];b[modify[t].position] = modify[t].now;}
}

莫队

register int stdl = 1, stdr = 0, stdt = 0, ans = 0, position;
//左指针、右指针、时间指针
for (int i = 1; i <= cnt; i++) {while (stdl > q[i].left) {stdl--;//operation 添加左端点}while (stdr < q[i].right) {stdr++;//operation 添加右端点}while (stdl < q[i].left) {//operation 删除左端点stdl++;}while (stdr > q[i].right) {//operation 删除右端点stdr--;}while (stdt < q[i].time) {stdt++;position = modify[stdt].position;//operation 修改位置if (position >= stdl && position <= stdr) {//operation 删除原贡献//operation 增加新贡献}}while (stdt > q[i].time) {position = modify[stdt].position;//operation 变回原来if (position >= stdl && position <= stdr) {//operation 删除新贡献//operation 增加原贡献}stdt--;}res[q[i].id] = ans;
}

模板题

P1903 数颜色 / 维护队列

Game

题意

你有$n$堆石子，每堆石子有$a_i$个石子

游戏规则：

• Alice 先选择一个大范围$[L,R]$区间内的石子

• Bob选择一个子区间$[l,r]$内的石子最终进行游戏

• 每次至少取走某一堆的一个石子，至多全部取走，无法移动石子者输(Nim 博弈)

  Alice先手，双方足够聪明

  问对Alice的每次选择$[Li,Ri]$，Bob有多少种选择能让Alice必胜

• 修改操作，即交换相邻的两堆石子

思路

Nim博弈

易知为他们进行的游戏为Nim博弈

要使Alice获胜，只需要区间异或和不为0即可

那么我们就可以去求他的补集，区间异或和为0的情况

带修莫队

• 数据范围为1e5，时间10s，可以接受带修莫队
• 单点修改，查询区间异或相同的个数，均可以由带修莫队实现
• 区间异或和为0的个数即为相同的前缀异或和对数
  因为计算前缀和的对数，所以要 left - 1，脑模一下就知道了
• 单点修改造成影响只对前一个的前缀和产生影响

代码

时间戳

struct Time {int x;		//修改位置int pre;	//原值int now;	//新值
}t[maxn];

离线询问

int block, belong[maxn];
struct Node {int left;int right;int time;int id;friend bool operator <(const Node& a, const Node& b) {return belong[a.left] == belong[b.left] ?(belong[a.right] == belong[b.right] ? a.time < b.time : 		//time为第三关键字a.right < b.right) :	//right为第二关键字a.left < b.left;		//left为第一关键字}
}q[maxn];

预处理

block = (int)pow(n, 2. / 3);	//带修莫队，常用block
for (int i = 1; i <= n; i++) {scanf("%d", &a[i]); b[i] = a[i];belong[i] = i / block;	//预处理blocksum[i] = sum[i - 1] ^ a[i];//前缀和r_sum[i] = sum[i];			//模拟前缀和
}
int cnt = 0, opt, T = 0;
for (int i = 1; i <= m; i++) {scanf("%d", &opt);if (opt == 1) {scanf("%d%d", &q[++cnt].left, &q[cnt].right);q[cnt].left--;q[cnt].time = T;q[cnt].id = cnt;}else {scanf("%d", &t[++T].x);		//在b[]和r_sum[]模拟修改，记录t[T].pre = r_sum[t[T].x];	t[T].now = r_sum[t[T].x] = r_sum[t[T].x + 1] ^ b[t[T].x];swap(b[t[T].x], b[t[T].x + 1]);}
}
sort(q + 1, q + 1 + cnt);

莫队

int stdl = 1, stdr = 0, stdt = 0; LL ans = 0;
register int position;
for (int i = 1; i <= cnt; i++) {while (stdl > q[i].left) ans = ans + col[sum[--stdl]]++;while (stdl < q[i].left) ans = ans - --col[sum[stdl++]];while (stdr < q[i].right) ans = ans + col[sum[++stdr]]++;while (stdr > q[i].right) ans = ans - --col[sum[stdr--]];while (stdt < q[i].time) {position = t[++stdt].x;sum[position] = t[stdt].now;	//更改值if (position >= q[i].left && position <= q[i].right) {ans = ans - --col[t[stdt].pre];	//修改贡献ans = ans + col[t[stdt].now]++;}}while (stdt > q[i].time) {position = t[stdt].x;sum[position] = t[stdt].pre;	//更改值if (position >= q[i].left && position <= q[i].right) {ans = ans - --col[t[stdt].now];//修改贡献ans = ans + col[t[stdt].pre]++;}stdt--;}res[q[i].id] = LL(q[i].right - q[i].left + 1) * (q[i].right - q[i].left) / 2 - ans;			//取补集
}

AC

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5e4 + 5;
struct Time {int x;int pre;int now;
}t[maxn];
int block, belong[maxn];
struct Node {int left;int right;int time;int id;friend bool operator <(const Node& a, const Node& b) {return belong[a.left] == belong[b.left] ?(belong[a.right] == belong[b.right] ? a.time < b.time : a.right < b.right) :a.left < b.left;}
}q[maxn];
int a[maxn], b[maxn], sum[maxn], r_sum[maxn];
int col[maxm];
LL res[maxn];
int main() {int n, m;while (~scanf("%d%d", &n, &m)) {memset(col, 0, sizeof(col));block = (int)pow(n, 2. / 3);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]); b[i] = a[i];belong[i] = i / block;sum[i] = sum[i - 1] ^ a[i];r_sum[i] = sum[i];}int cnt = 0, opt, T = 0;for (int i = 1; i <= m; i++) {scanf("%d", &opt);if (opt == 1) {scanf("%d%d", &q[++cnt].left, &q[cnt].right);q[cnt].left--;q[cnt].time = T;q[cnt].id = cnt;}else {scanf("%d", &t[++T].x);t[T].pre = r_sum[t[T].x];t[T].now = r_sum[t[T].x] = r_sum[t[T].x + 1] ^ b[t[T].x];swap(b[t[T].x], b[t[T].x + 1]);}}sort(q + 1, q + 1 + cnt);int stdl = 1, stdr = 0, stdt = 0; LL ans = 0;register int position;for (int i = 1; i <= cnt; i++) {while (stdl > q[i].left) ans = ans + col[sum[--stdl]]++;while (stdl < q[i].left) ans = ans - --col[sum[stdl++]];while (stdr < q[i].right) ans = ans + col[sum[++stdr]]++;while (stdr > q[i].right) ans = ans - --col[sum[stdr--]];while (stdt < q[i].time) {position = t[++stdt].x;sum[position] = t[stdt].now;if (position >= q[i].left && position <= q[i].right) {ans = ans - --col[t[stdt].pre];ans = ans + col[t[stdt].now]++;}}while (stdt > q[i].time) {position = t[stdt].x;sum[position] = t[stdt].pre;if (position >= q[i].left && position <= q[i].right) {ans = ans - --col[t[stdt].now];ans = ans + col[t[stdt].pre]++;}stdt--;}res[q[i].id] = LL(q[i].right - q[i].left + 1) * (q[i].right - q[i].left) / 2 - ans;}for (int i = 1; i <= cnt; i++)printf("%lld\n", res[i]);}
}