mo-algo-Notes

普通莫队

本质

假设有两个区间 $[l_1,r_1],[l_2,r_2]$，我们已知 $[l_1,r_1]$ 的答案，如果我们能 $O(x)$ 转移到 $[l+1,r],[l-1,r],[l,r+1],[l,r-1]$，那么就没有比较暴力 $O(n)$ 计算下一个区间的答案，我们有期望更优的 $O(x\times(|l_1-l_2|+|r_1-r_2|))$。

观察这个式子其实不难发现，莫队的本质就是一个二维扫描线，即可以在 $(x,y)$ 两轴上任意滑动。而我们的询问就是平面上的单点。

最优解是 NPC 问题，但是莫队算法已经给出了一个比较好的解，即对序列分块，然后对询问按块排序（左端点块为第一关键字，右端点位置为第二关键字）。

可以证明复杂度为 $O(n\sqrt m+m\log m+m)$ 的，具体分讨左右指针的移动复杂度即可。

一些优化

奇偶化排序

普通莫队的右指针每次移到最右边之后还要回来才能进行下一个块的询问，这里做出一个优化，即块的编号是奇数时右端点按正序排，编号为偶数时右端点按逆序排。

据 lxl 说这样能快三分之一。

块长

这个属于玄学优化了。

但是有些题里块长是用来平衡复杂度的，确实不同。

但是据 lxl 说把块长调到 $\displaystyle\frac{n}{\sqrt{\frac{2m}{3}}}$ 可以快 10%。

内存连续访问

这个东西感觉没用。

就是比如说在数颜色的时候，可以记录颜色的前驱和后继，然后每次访问前驱后继是内存连续的，访问颜色数组是内存不连续的，所以就能优化。

但是感觉大多数莫队都是没法使用这种优化的。

例题

P1494 小 Z 的袜子

典题。

直接暴力转移就是 $O(1)$ 的。

// Problem: P1494 [国家集训队] 小 Z 的袜子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1494
// Memory Limit: 128 MB
// Time Limit: 200000 ms
// Start coding at 2023-12-15 14:42:47
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt[100001];
int base;
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?r<a.r:l<a.l;
	}
}Q[200001];
int n,q;
pair<int,int> ans[100001];
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int colo[100001],res;
void add(int x){
	res+=cnt[x];
	cnt[x]++;
	// cerr<<"add"<<x<<" "<<res<<"\n";
	return;
}
void del(int x){
	cnt[x]--;
	res-=cnt[x];
	// cerr<<"del"<<x<<" "<<res<<"\n";
	return;
}
void addL(int x){
	// if(x==0)return;
	add(colo[x]);
	return;
}
void delL(int x){
	// if(x==0)return;
	del(colo[x]);
	return;
}
void addR(int x){
	// if(x==0)return;
	add(colo[x]);
	return;
}
void delR(int x){
	// if(x==0)return;
	del(colo[x]);
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>colo[i];
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	base=sqrt(n);
	sort(Q+1,Q+q+1);
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l>l&&l<r)delL(l++);
			while(Q[i].l<l)addL(--l);
			while(Q[i].r>r)addR(++r);
			while(Q[i].r<r&&l<r)delR(r--);
		}
		// cerr<<res<<"\n";
		ans[Q[i].id].first=res;
		int len=r-l+1;
		ans[Q[i].id].second=len*(len-1)/2;
	}
	for(int i=1;i<=q;i++){
		if(ans[i].second==0)ans[i].second++;
		int g=gcd(ans[i].first,ans[i].second);
		// cerr<<g<<"\n";
		cout<<ans[i].first/g<<"/"<<ans[i].second/g<<"\n";
	}
	return 0;
}

P4396 作业

考虑莫队其实是一种 $O(n\sqrt m)$ 次修改，$O(m)$ 次询问的数据结构，那么有些时候为了复杂度平衡要使用 $O(x)$ 修改，$O(x\sqrt n)$ 或 $O(x\log^kn)$ 查询的数据结构来平衡复杂度。

这道题就是一个典型的例子，考虑正常做法就是莫队 + 值域线段树，时间复杂度 $O(n\sqrt m\log V)$，但是如果套用值域分块，那么复杂度变为 $O(n\sqrt m+m\sqrt n)$，可以通过。

这里的值域分块较为简单，就是在本身数上打标记且在块上统计和，询问正常走一遍即为 $O(1)-O(\sqrt n)$。

// Problem: P4396 [AHOI2013] 作业
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4396
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-15 16:27:58
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m,base,B;
struct qu{
	int l,r,ll,rr,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?r<a.r:l<a.l;
	}
}Q[200001];
int ans1[200001],ans2[200001];
int num[100005];
int belong[100005],st[100005],ed[100005];
int cnt[100005],cntn[100005];
void insert(int x){
	num[x]++;
	if(num[x]==1)cntn[belong[x]]++;
	cnt[belong[x]]++;
	return;
}
void deletex(int x){
	num[x]--;
	if(num[x]==0)cntn[belong[x]]--;
	cnt[belong[x]]--;
	return;
}
pair<int,int> ask(int l,int r){
	int res1=0,res2=0;
	int Lb=belong[l],Rb=belong[r];
	if(Lb==Rb){
		for(int i=l;i<=r;i++){
			res1+=num[i];
			res2+=(num[i]>0);
		}
		return make_pair(res1,res2);
	}
	for(int i=l;i<=ed[Lb];i++){
		res1+=num[i];
		res2+=(num[i]>0);
	}
	for(int i=Lb+1;i<=Rb-1;i++){
		res1+=cnt[i];
		res2+=cntn[i];
	}
	for(int i=st[Rb];i<=r;i++){
		res1+=num[i];
		res2+=(num[i]>0);
	}
	return make_pair(res1,res2);
}
int val[100001];
void add(int x){
	insert(val[x]);
	return;
}
void del(int x){
	deletex(val[x]);
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	base=sqrt(n);
	B=sqrt(N);
	int C=N/B;
	for(int i=1;i<=C;i++){
		st[i]=(i-1)*B+1;
		ed[i]=i*B;
		for(int j=st[i];j<=ed[i];j++){
			belong[j]=i;
		}
	}
	if(N%B){
		++C;
		st[C]=(C-1)*B+1;
		ed[C]=N;
		for(int j=st[C];j<=ed[C];j++){
			belong[j]=C;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>val[i];
	}
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r>>Q[i].ll>>Q[i].rr;
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1);
	int l=1,r=0;
	// return 0;
	for(int i=1;i<=m;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l>l&&l<r)del(l++);
			while(Q[i].l<l)add(--l);
			while(Q[i].r>r)add(++r);
			while(Q[i].r<r&&l<r)del(r--);
			// cerr<<l<<" "<<r<<" "<<Q[i].l<<" "<<Q[i].r<<"\n";
		}
		auto temp=ask(Q[i].ll,Q[i].rr);
		// cerr<<temp.first<<" "<<temp.second<<"\n";
		ans1[Q[i].id]=temp.first;
		ans2[Q[i].id]=temp.second;
	}
	for(int i=1;i<=m;i++){
		cout<<ans1[i]<<" "<<ans2[i]<<"\n";
	}
	return 0;
}

P4462

做异或前缀和，发现就是统计区间内 $a_{l-1}\otimes a_r=k$ 的个数。将询问区间变为 $[l-1,r]$，发现其实这种情况下只囊括了 $[l,r]$ 的信息，直接莫队维护就行了。

// Problem: P4462 [CQOI2018] 异或序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4462
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-16 11:27:34
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,base;
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?r<a.r:l<a.l;
	}
}Q[1000001];
int colo[1000001],pre[1000001],buc[10000001],k;
int ans[1000001];
int res;
void add(int x){
	res+=buc[pre[x]^k],buc[pre[x]]++;
	return;
}
void del(int x){
	buc[pre[x]]--,res-=buc[pre[x]^k];
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>colo[i],pre[i]=colo[i];
	for(int i=1;i<=n;i++)pre[i]^=pre[i-1];
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
		Q[i].l--;
	}
	base=sqrt(n);
	sort(Q+1,Q+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l<l)add(--l);
			while(Q[i].l>l&&l<r)del(l++);
			while(Q[i].r<r&&l<r)del(r--);
			while(Q[i].r>r)add(++r);
		}
		ans[Q[i].id]=res;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

P4689 这是我自己的发明

对于换根，直接在求解时分讨即可。

对于询问，拍到 dfs 序上，然后进行 $root$ 在 $u$ 的儿子的子树里，就是 $u$，和不在 $u$ 子树里进行分讨，每种区间暴力拆前缀和添加询问，每次最多有 $9$ 个询问。

时间复杂度 O(n\sqrt {km}+km\log m+m)(k_\max=9)。

// Problem: P4689 [Ynoi2016] 这是我自己的发明
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4689
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// Start coding at 2023-12-16 15:27:49
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct line{
	int to,link;
}E[200005];
int head[100005],tot=1;
void addE(int u,int v){
	E[++tot].link=head[u];
	E[tot].to=v;
	head[u]=tot;
	return;
}
int dfncnt;
int L[100001],R[100001],rk[100001];
int dep[100001],fa[100001][21],siz[100001];
void dfs(int now,int f){
	fa[now][0]=f;
	siz[now]=1;
	L[now]=++dfncnt;
	rk[dfncnt]=now;
	for(int i=0;fa[now][i];)i++,fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=E[i].link){
		if(E[i].to==f)continue;
		dep[E[i].to]=dep[now]+1;
		dfs(E[i].to,now);
		siz[now]+=siz[E[i].to];
	}
	R[now]=dfncnt;
	return;
}
int n,m;
int base;
struct qu{
	int l,r,id;
	bool o;
	void inp(int _l,int _r,int _id,bool _o){
		if(_l>_r)swap(_l,_r);
		l=_l,r=_r,id=_id,o=_o;
		return;
	}
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l; 
	}
}Q[5000005];
int colo[100001],org[100001];
int ans[1000001],res;
int cnt1[100001],cnt2[100001];
void addL(int x){
	x=rk[x];
	res+=cnt2[colo[x]];
	cnt1[colo[x]]++;
	return;
}
void addR(int x){
	x=rk[x];
	res+=cnt1[colo[x]];
	cnt2[colo[x]]++;
	return;
}
void delL(int x){
	x=rk[x];
	res-=cnt2[colo[x]];
	cnt1[colo[x]]--;
	return;
}
void delR(int x){
	x=rk[x];
	res-=cnt1[colo[x]];
	cnt2[colo[x]]--;
	return;
}
struct ran{
	int l,r;
	bool id;
	void inp(int _x,int _y){
		if(_y<_x)return;
		l=_x,r=_y,id=1;
		return;
	}
	void clear(){
		l=r=id=0;
		return;
	}
};
ran X1,X2,Y1,Y2;
int qcnt=0,rt=1;
int find(int x,int goal){
	for(int i=20;i>=0;i--){
		if(dep[fa[x][i]]>dep[goal])x=fa[x][i];
		// cerr<<x<<"\n";
	}
	return x;
}
void qadd(ran r1,ran r2,int id){
	// cerr<<"in "<<qcnt<<"\n";
	Q[++qcnt].inp(r1.r,r2.r,id,1);
	if(r1.l!=1)Q[++qcnt].inp(r1.l-1,r2.r,id,0);
	if(r2.l!=1)Q[++qcnt].inp(r1.r,r2.l-1,id,0);
	if(r1.l!=1&&r2.l!=1)Q[++qcnt].inp(r1.l-1,r2.l-1,id,1);
	// cerr<<"out "<<qcnt<<"\n";
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>colo[i];
		org[i]=colo[i];
	}
	sort(org+1,org+n+1);
	int ocnt=unique(org+1,org+n+1)-org-1;
	for(int i=1;i<=n;i++){
		colo[i]=lower_bound(org+1,org+ocnt+1,colo[i])-org;
	}
	base=n/sqrt(m);
	if(base==0)base=sqrt(n);
	int op,x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		addE(x,y);
		addE(y,x);
	}
	dfs(1,0);
	int _2=0;
	for(int i=1;i<=m;i++){
		cin>>op>>x;
		if(op==1){
			rt=x;
		}else{
			_2++;
			cin>>y;
			// cerr<<_2<<"\n";
			X1.clear(),X2.clear(),Y1.clear(),Y2.clear();
			if(L[rt]<L[x]||L[rt]>R[x])X1.inp(L[x],R[x]);
			else if(L[rt]==L[x])X1.inp(1,n);
			else{
				int so=find(rt,x);
				X1.inp(1,L[so]-1);
				X2.inp(R[so]+1,n);
			}
			if(L[rt]<L[y]||L[rt]>R[y])Y1.inp(L[y],R[y]);
			else if(L[rt]==L[y])Y1.inp(1,n);
			else{
				int so=find(rt,y);
				Y1.inp(1,L[so]-1);
				Y2.inp(R[so]+1,n);
			}
			// cerr<<"stadd\n";
			qadd(X1,Y1,_2);
			if(X2.id)qadd(X2,Y1,_2);
			if(Y2.id)qadd(X1,Y2,_2);
			if(X2.id&&Y2.id)qadd(X2,Y2,_2);
		}
	}
	// return 0;
	sort(Q+1,Q+qcnt+1);
	// return 0;
	int l=0,r=0;
	for(int i=1;i<=qcnt;i++){
		int oo=(Q[i].o?1:-1);
		while(Q[i].l<l)delL(l--);
		while(Q[i].l>l)addL(++l);
		while(Q[i].r<r)delR(r--);
		while(Q[i].r>r)addR(++r);
		// cout<<oo<<" "<<res<<" "<<Q[i].l<<" "<<Q[i].r<<" "<<Q[i].id<<"\n";
		ans[Q[i].id]+=oo*res;
	}
	for(int i=1;i<=_2;i++)cout<<ans[i]<<"\n";
	return 0;
}

使用基数排序能做到更为优秀的复杂度。

JOISC2014 历史研究

考虑对于所有可能出现的答案进行离散化，那么就可以使用值域分块平衡复杂度。

$O(1)-O(\sqrt n)$ 查询最大值即可。

// Problem: 歴史の研究
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_joisc2014_c
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Start coding at 2023-12-17 20:24:56
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct numb{
	int num,mul,org;
	bool operator <(const numb &a) const{
		return num<a.num;
	}
}O[100005];
int typ[100005];
int n,q;
int base,B,C;
unordered_map<int,int> t,xiab;
int vcnt;
vector<int> rec[100001];
int bsum[100001];
int cnt[100001],belong[100001];
int st[100001],ed[100001];
// int org[100001];
void insert(int x){
	// cerr<<x<<"\n";
	cnt[x]++;
	bsum[belong[x]]++;
	return;
}
void deletex(int x){
	cnt[x]--;
	bsum[belong[x]]--;
	return;
}
int ask(){
	int p;
	for(p=C;p>=1;p--)if(bsum[p])break;
	if(p==0)return 0;
	for(int o=ed[p];o>=st[p];o--){
		if(cnt[o])return O[o].num;
	}
	return 0;
}
void add(int x){
	int nu=typ[x],kk=t[nu];
	t[nu]++;
	if(kk)deletex(rec[xiab[nu]][kk-1]);
	insert(rec[xiab[nu]][kk]);
	return;
}
void del(int x){
	int nu=typ[x],kk=t[nu];
	t[nu]--;
	deletex(rec[xiab[nu]][kk-1]);
	if(kk>1)insert(rec[xiab[nu]][kk-2]);
	return;
}
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r<a.r:r>a.r):l<a.l;
	}
}Q[100001];
int ans[100001];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>typ[i];
		t[typ[i]]++;
		// org[i]=typ[i]*t[typ[i]];
		O[i]={typ[i]*t[typ[i]],t[typ[i]],typ[i]};
		if(!xiab[typ[i]]){
			xiab[typ[i]]=++vcnt;
		}
	}
	// sort(org+1,org+n+1);
	sort(O+1,O+n+1);
	t.clear();
	for(int i=1;i<=n;i++){
		rec[xiab[O[i].org]].push_back(i);
	}
	B=sqrt(n);
	C=n/B;
	for(int i=1;i<=C;i++){
		st[i]=(i-1)*B+1;
		ed[i]=i*B;
		for(int j=st[i];j<=ed[i];j++)belong[j]=i;
	}
	if(n%B){
		C++;
		st[C]=(C-1)*B+1;
		ed[C]=n;
		for(int j=st[C];j<=ed[C];j++){
			belong[j]=C;
		}
	}
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	base=n/sqrt(q);
	if(base==0)base=sqrt(n);
	sort(Q+1,Q+q+1);
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l>l&&l<r)del(l++);
			while(Q[i].l<l)add(--l);
			while(Q[i].r>r)add(++r);
			while(Q[i].r<r&&l<r)del(r--);
		}
		ans[Q[i].id]=ask();
		// cerr<<Q[i].l<<" "<<Q[i].r<<"\n";
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}

P5072 盼君勿忘

考虑莫队维护每个数的贡献次数，假如说该数出现了 $k$ 次，那么该数对答案的贡献就是 $(2^{r-l+1}-2^{r-l+1-k})\times num$。不难发现这样做的复杂度是 $O(n\sqrt m+mn\log n)$ 的，具体就是统计答案时使用快速幂并且将值域上的数全部统计一遍。

对于统计值域上的优化，考虑使用根号分治。对于 $\leq \sqrt n$ 的数，统计它们在相同出现次数下的和，对于 $> \sqrt n$ 的数，暴力记录这些数及其出现次数。

对于求幂的优化，考虑对于每一个模数，我们都只有 $O(\sqrt n)$ 的时间处理，而统计答案占用的时间已达到了 $O(\sqrt n)$，因此，我们必须在 $O(\sqrt n)-O(1)$ 时间内求得快速幂。考虑底数固定，使用分块的思想把值域分成 $\sqrt n$ 块，记录每一块的开头此时的幂，即 2^\sqrt n,2^{2\sqrt n}...,2^{\sqrt n\times\sqrt n}，然后再预处理 $2^0,2^1\cdots,2^{\sqrt n-1}$ 即能 $O(1)$ 查询幂。

通过上面一堆优化，最终我们的时间复杂度就是 $O(n\sqrt m+m\sqrt n)$，不过常数较大。

// Problem: P5072 [Ynoi2015] 盼君勿忘
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5072
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// Start coding at 2023-12-18 16:30:19
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,base,B,C;
int sml[100001],blst[100001];
void init(int p){
	sml[0]=blst[0]=1;
	for(int i=1;i<=B-1;i++)sml[i]=sml[i-1]*2%p;
	blst[1]=sml[B-1]*2;
	for(int i=2;i<=C;i++)blst[i]=blst[i-1]*blst[1]%p;
	return;
}
int _2(int x){
	return blst[x/B]*sml[x%B];
}
struct qu{
	int l,r,p,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l;
	}
}Q[100001];
int colo[100001],ans[100001];
unordered_set<int> oversqrt;
int cnt[100001];
int summ[100001];
void add(int x){
	if(cnt[colo[x]]>B){
		return cnt[colo[x]]++,void();
	}
	summ[cnt[colo[x]]]-=colo[x];
	cnt[colo[x]]++;
	if(cnt[colo[x]]>B)oversqrt.insert(colo[x]);
	else summ[cnt[colo[x]]]+=colo[x];
	return;
}
void del(int x){
	if(cnt[colo[x]]<=B)summ[cnt[colo[x]]]-=colo[x];
	cnt[colo[x]]--;
	if(cnt[colo[x]]<=B){
		if(cnt[colo[x]]==B)oversqrt.erase(colo[x]);
		summ[cnt[colo[x]]]+=colo[x];
	}
	return;
}
int getans(int len,int p){
	int res=0;
	for(int i=1;i<=B;i++)res=(res+((_2(len)-_2(len-i))%p+p)%p*summ[i])%p;
	for(auto i:oversqrt)res=(res+((_2(len)-_2(len-cnt[i]))%p+p)%p*i)%p;
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	B=sqrt(n);
	C=n/B;
	base=n/sqrt(q);
	if(base==0)base=sqrt(n);
	for(int i=1;i<=n;i++)cin>>colo[i];
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r>>Q[i].p;
		Q[i].id=i;
	}
	sort(Q+1,Q+q+1);
	// return 0;
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		init(Q[i].p);
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l>l&&l<r)del(l++);
			while(Q[i].l<l)add(--l);
			while(Q[i].r>r)add(++r);
			while(Q[i].r<r&&l<r)del(r--);
		}
		ans[Q[i].id]=getans(Q[i].r-Q[i].l+1,Q[i].p);
		// cerr<<Q[i].l<<" "<<Q[i].r<<" "<<(int)oversqrt.size()<<"\n";
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}

P3245 大数

考虑使用数据分治。对于莫队，考虑不难发现 $s[l\cdots n]\equiv s[r+1\cdots n]\pmod p$，有 $s[l\cdots r]\times 10^{n-r-1}\equiv 0\pmod p$，可以使用后缀和使这道题变成小 z 的袜子。（其实可以不难发现前缀和不行，因为此时 $s[l\cdots r]+10^k\times s[1\cdots l-1]=s[1\cdots r]$，发现不可做。）

考虑到当 $p$ 为 $2$ 或 $5$ 时这种方法会算漏，那么可以使用其他方法，比如对于 $p=2$，统计末位为 $0,2,4,6,8$ 的数，可以使用前缀和做到 $O(m+n)$。

总时间复杂度为 $O(n\sqrt m)$。

// Problem: P3245 [HNOI2016] 大数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3245
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-19 09:14:13
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p;
int colo[200001],org[200001];
int base;
char s[200001];
namespace _1{
	//for p=2/5
	int gx[11];
	int pre[200005],presum[200005];
	void solve(){
		if(p==2)gx[0]=gx[2]=gx[4]=gx[6]=gx[8]=1;
		else gx[0]=gx[5]=1;
		for(int i=1;i<=n;i++){
			pre[i]=pre[i-1]+gx[s[i]-'0'];
			presum[i]=presum[i-1]+gx[s[i]-'0']*i;
		}
		int l,r;
		while(m--){
			cin>>l>>r;
			cout<<presum[r]-presum[l-1]-(pre[r]-pre[l-1])*(l-1)<<"\n";
		}
		exit(0);
	}
}
namespace _2{
	struct qu{
		int l,r,id;
		bool operator <(const qu &a) const{
			return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l;
		}
	}Q[200001];
	long long now=0,res=0;
	int cnt[200001],ans[200001];
	void add(int x){
		// cerr<<"add "<<x<<"\n";
		if(cnt[colo[x]]!=0)res-=cnt[colo[x]]*(cnt[colo[x]]-1)/2;
		cnt[colo[x]]++;
		res+=cnt[colo[x]]*(cnt[colo[x]]-1)/2;
		// cerr<<res<<"\n";
		return;
	}
	void del(int x){
		res-=cnt[colo[x]]*(cnt[colo[x]]-1)/2;
		cnt[colo[x]]--;
		if(cnt[colo[x]]!=0)res+=cnt[colo[x]]*(cnt[colo[x]]-1)/2;
		return;
	}
	int _10[200001]={1};
	void solve(){
		for(int i=1;i<=n;i++)_10[i]=_10[i-1]*10%p;
		for(int i=1;i<=m;i++){
			cin>>Q[i].l>>Q[i].r;
			Q[i].id=i;
			Q[i].r++;
		}
		base=n/sqrt(m);
		if(base==0)base=sqrt(n);
		sort(Q+1,Q+m+1);
		for(int i=n;i>=1;i--){
			now+=(s[i]-'0')*_10[n-i];
			now%=p;
			colo[i]=org[i]=now;
			// now*=10;''
			// cerr<<colo[i]<<"\n";
		}
		n++;
		sort(org+1,org+n+1);
		int ocnt=unique(org+1,org+n+1)-org-1;
		for(int i=1;i<=n;i++)colo[i]=lower_bound(org+1,org+ocnt+1,colo[i])-org;
		int l=1,r=0;
		for(int i=1;i<=m;i++){
			while(l!=Q[i].l||r!=Q[i].r){
				while(Q[i].l>l&&l<r)del(l++);
				while(Q[i].l<l)add(--l);
				while(Q[i].r>r)add(++r);
				while(Q[i].r<r&&l<r)del(r--);
			}
			ans[Q[i].id]=res;
		}
		for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
		exit(0);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>p>>(s+1);
	n=strlen(s+1);
	cin>>m;
	if(p==2||p==5)_1::solve();
	else _2::solve();
	return 0;
}

P1997

区间众数板子题。

直接维护颜色的桶和出现次数的桶，暴力记录+转移最大值即可。

// Problem: P1997 faebdc 的烦恼
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1997
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-19 10:55:24
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int cnt[200001],bcnt[100001];
int colo[100001];
int n,q,base;
int res=0;
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l;
	}
}Q[200001];
int ans[200001];
void add(int x){
	bcnt[cnt[colo[x]]]--;
	cnt[colo[x]]++;
	bcnt[cnt[colo[x]]]++;
	if(res<cnt[colo[x]])res=cnt[colo[x]];
	return;
}

void del(int x){
	bcnt[cnt[colo[x]]]--;
	cnt[colo[x]]--;
	bcnt[cnt[colo[x]]]++;
	if(bcnt[res]==0)res--;
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>colo[i];
		colo[i]+=1e5;
	}
	for(int i=1;i<=q;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	base=n/sqrt(q);
	if(base==0)base=sqrt(n);
	int l=1,r=0;
	for(int i=1;i<=q;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(Q[i].l>l&&l<r)del(l++);
			while(Q[i].l<l)add(--l);
			while(Q[i].r>r)add(++r);
			while(Q[i].r<r)del(r--);
		}
		ans[Q[i].id]=res;
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}

莫队二次离线

我不知道为什么要先学这个，据说是所有莫队中最抽象的一个。但是 lxl PPT 先讲到这个就先学吧。

看了将近一个下午才基本看懂，可见是有多抽象。

考虑普通莫队复杂度瓶颈大多在移动指针处，而莫队二离就是来优化这个过程的。

前提

要保证每个点对区间的贡献可差分，即 $f(p,[l,r])=f(p,[1,r])-f(p,[1,l-1])$。

还有就是普通莫队的转移复杂度较高，达到了单次 $O(x)$ 而通过不了题时，莫队二离可以将复杂度降到 $O(n\sqrt m+nx)$。

思路

就是一个类似于莫队 + 扫描线的东西。

考虑每次转移时可以如何拆贡献：

以 $[l,r]\to [l,r+1]$ 为例，考虑此时加入的贡献就是 $f(r+1,[1,r])-f(r+1,[1,l-1])$，而减号前的那部分贡献可以预处理。

令预处理出那部分的前缀和为 $pre1$（$f(k,[1,k-1])$），那么 $[l,r]\to [l,r'](r'>r)$ 多出来的贡献就是 $pre1_{r'}-pre1_{r}-\sum_{i=r+1}^{r'}f(i,[1,l-1])$。考虑将询问离线下来做扫描线，把询问挂到 $l-1$ 处，然后暴力计算 $\sum_{i=r+1}^{r'}f(i,[1,l-1])$。由于莫队这样移动指针最多 $n\sqrt m$ 次，所以这个东西最多被计算 $n\sqrt m$ 次。

其他 $3$ 种情况对于该情况基本相同，下面简述一下：

对于 $[l,r]\to[l,r-1]$，此时去除的贡献是 $f(r,[1,r-1])-f(r,[1,l-1])$。（就是上面加入的逆操作）

那么对于 $[l,r]\to[l,r'](r'<r)$，去掉的贡献一共是 $pre1_r-pre1_{r'}-\sum_{i=r'+1}^rf(i,[1,l-1])$，同样扫描线即可。

对于 $[l,r]\to[l-1,r]$，加入的贡献是 $f(l-1,[1,r])-f(l-1,[1,l-1])$，同样的，减号后面那一部分的贡献可以预处理，记其前缀和为 $pre2$（$f(k,[1,k])$）。

那么对于 $[l,r]\to[l',r](l'<l)$，此时加入总贡献为 $\sum_{i=l'}^{l-1}f(i,[1,r])-(pre2_{l-1}-pre2_{l'-1})$，把询问放到 $r$ 处扫描线。

对于 $[l,r]\to[l+1,r]$，去除的贡献为 $f(l,[1,r])-f(l,[1,l])$。（同样是上面加入的逆操作）

那么对于 $[l,r]\to[l',r](l'>l)$，此时去除的贡献为 $\sum_{i=l}^{l'-1}f(i,[1,r])-(pre2_{l'-1}-pre2_{l-1})$。

利用扫描线模拟莫队即可。

上面的式子经过多次修改，但仍极容易出错，如有误请及时指出。

例题

P4887 【模板】莫队二次离线

方法和上面讲的一模一样，此时 $O(x)=O(C_{14}^k)$。预处理有 $k$ 个 $1$ 的数，扫描线时每次把这些数异或原数后的值放入桶中，更新两个前缀和，然后暴力回答二离出的询问即可。

// Problem: P4887 【模板】莫队二次离线（第十四分块(前体)）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4887
// Memory Limit: 40 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-19 20:11:50
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int _k[16385],kcnt;
int n,m,k,base;
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return (l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l);
	}
}Q[100001];
int res[100001][2];//0->l move|||||| 1->r move
int ans[100001],colo[100001];
int cnt[100001];
struct qu2{
	int l,r,id,wh;
}Q2[1000001];
vector<int> v[100001];
int q2cnt;
int sum1[100001],sum2[100001];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	for(int i=0;i<16384;i++)if(__builtin_popcount(i)==k)_k[++kcnt]=i;
	base=n/sqrt(m);
	if(base==0)base=sqrt(n);
	for(int i=1;i<=n;i++)cin>>colo[i];
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1);
	int l=2,r=1;
	for(int i=1;i<=m;i++){
		if(l<Q[i].l)Q2[++q2cnt]={l,Q[i].l-1,i,0};
		else Q2[++q2cnt]={Q[i].l,l-1,i,0};
		v[r].push_back(q2cnt);
		l=Q[i].l;
		if(r<Q[i].r)Q2[++q2cnt]={r+1,Q[i].r,i,1};
		else Q2[++q2cnt]={Q[i].r+1,r,i,1};
		v[l-1].push_back(q2cnt);
		r=Q[i].r;
	}
	for(int i=1;i<=n;i++){
		sum1[i]=sum1[i-1]+cnt[colo[i]];
		for(int j=1;j<=kcnt;j++)cnt[colo[i]^_k[j]]++;
		sum2[i]=sum2[i-1]+cnt[colo[i]];
		for(auto p:v[i]){
			for(int j=Q2[p].l;j<=Q2[p].r;j++){
				res[Q2[p].id][Q2[p].wh]+=cnt[colo[j]];
			}
		}
	}
	l=2,r=1;
	int nowans=0;
	for(int i=1;i<=m;i++){
		if(l<Q[i].l)nowans+=(sum2[Q[i].l-1]-sum2[l-1])-res[i][0];
		else nowans+=res[i][0]-(sum2[l-1]-sum2[Q[i].l-1]);
		l=Q[i].l;
		if(r<Q[i].r)nowans+=(sum1[Q[i].r]-sum1[r])-res[i][1];
		else nowans+=res[i][1]-(sum1[r]-sum1[Q[i].r]);
		r=Q[i].r;
		ans[Q[i].id]=nowans;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

P5047 区间逆序对

这道题的经典做法就是莫队 + 值域线段树，时间复杂度 $O(n\sqrt m\log n)$，考虑用二离来优化这个过程。

我们知道普通莫队就是 $O(n\sqrt m)$ 次移动指针，那么就有 $O(n\sqrt m)$ 次插入元素和查询贡献。而莫队二离借用了扫描线的思想，把复杂度降为 $O(n)$ 次插入元素，$O(n\sqrt m)$ 次查询贡献。为了平衡复杂度，我们就可以用一个 $O(\sqrt n)-O(1)$ 的值域分块来维护插入元素和查询贡献。

查询贡献主要就是查询就多少数严格大于或小于所查询的数，记录每个块内的前后缀和和块的前后缀和，每次插入时暴力更新前后缀和，时间复杂度 $O(\sqrt n)-O(1)$，总时间复杂度 $O(n\sqrt n+n\sqrt m)$。

但是！

注意此时 $[l,r]\to[l+1,r]$ 类操作该如何处理。注意到原来我们用的式子是 $f(l,[1,r])-f(l,[1,l])$，而这道题中其实 $f(l,[1,r])$ 无法快速被计算，因为无法定义这个贡献是查找严格大于还是严格小于，所以需要使用其他方法规避这种情况。

考虑使用后缀和。那么 $[l,r]\to[l+1,r]$ 所失去的贡献就是 $f(l,[l+1,n])-f(l,[r+1,n])$，$[l,r]\to[l-1,r]$ 所加入的贡献为 $f(l-1,[l,n])-f(l-1,[r+1,n])$，不难想到令 $suf_i$ 为 $f(i-1,[i,n])$ 的后缀和。

那么对于 $[l,r]\to[l',r](l'>l)$，去除的贡献为 $suf_{l}-suf_{l'}-\sum_{i=l}^{l'-1}f(i,[r+1,n])$，这时成功规避上面的问题了。（注意后缀和是倒着减的）

对于 $[l,r]\to[l',r](l'<l)$，加入的贡献为 $suf_{l'}-suf_{l}-\sum_{i=l'}^{l-1}f(i,[r+1,n])$，询问挂到 $r+1$ 处，扫描线正着倒着都扫一遍即可。

// Problem: P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5047
// Memory Limit: 31 MB
// Time Limit: 250000 ms
// Start coding at 2023-12-20 15:32:02
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int colo[100001],org[100001],n,m;
int B,C,base;
int belong[100005],k1[100005],a1[100005],st[100005],ed[100005];//严格小于-前缀和
int k2[100005],a2[100005];//严格大于-后缀和
void insert1(int x){
	int bx=belong[x];
	for(int i=x;i<=ed[bx];i++)a1[i]++;
	for(int i=bx;i<=C;i++)k1[i]++;
	return;
}
void delete1(int x){
	int bx=belong[x];
	for(int i=x;i<=ed[bx];i++)a1[i]--;
	for(int i=bx;i<=C;i++)k1[i]--;
	return;
}
int ask1(int x){
	int bx=belong[x];
	int res=k1[bx-1];
	int ext=0;
	if(x!=st[bx])ext=a1[x-1];
	return res+ext;
}
void insert2(int x){
	int bx=belong[x];
	for(int i=st[bx];i<=x;i++)a2[i]++;
	for(int i=1;i<=bx;i++)k2[i]++;
	return;
}
void delete2(int x){
	int bx=belong[x];
	for(int i=st[bx];i<=x;i++)a2[i]--;
	for(int i=1;i<=bx;i++)k2[i]--;
	return;
}
int ask2(int x){
	int bx=belong[x];
	int res=k2[bx+1];
	int ext=0;
	if(x!=ed[bx])ext=a2[x+1];
	return res+ext;
}
int pre[100005],suf[100005];
struct qu{
	int l,r,id;
	bool operator <(const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l;
	}
}Q[100001];
int ans[100001];
int res[100001][2];
struct quf{
	int l,r,id;
}Q1[500001];
int q1cnt,q2cnt;
struct qub{
	int l,r,id;
}Q2[500001];
vector<int> v1[100005],v2[100005];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	base=n/sqrt(m);
	if(base==0)base=sqrt(n);
	B=sqrt(n);
	C=n/B;
	for(int i=1;i<=n;i++){
		cin>>colo[i];
		org[i]=colo[i];
	}
	sort(org+1,org+n+1);
	int ocnt=unique(org+1,org+n+1)-org-1;
	for(int i=1;i<=n;i++){
		colo[i]=lower_bound(org+1,org+ocnt+1,colo[i])-org;
	}
	for(int i=1;i<=C;i++){
		st[i]=(i-1)*B+1;
		ed[i]=i*B;
		for(int j=st[i];j<=ed[i];j++)belong[j]=i;
	}
	if(n%B){
		C++;
		st[C]=(C-1)*B+1;
		ed[C]=n;
		for(int j=st[C];j<=ed[C];j++)belong[j]=C;
	}
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1);
	int l=2,r=1;
	for(int i=1;i<=m;i++){
		if(l<Q[i].l)Q1[++q1cnt]={l,Q[i].l-1,i};
		else Q1[++q1cnt]={Q[i].l,l-1,i};
		l=Q[i].l;
		v1[r+1].push_back(q1cnt);
		if(r<Q[i].r)Q2[++q2cnt]={r+1,Q[i].r,i};
		else Q2[++q2cnt]={Q[i].r+1,r,i};
		r=Q[i].r;
		v2[l-1].push_back(q2cnt);
	}
	// insert2(2),insert2(3);
	// cout<<ask2(4)<<" "<<ask2(1)<<" "<<ask2(2)<<"\n";
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+ask2(colo[i]);
		insert2(colo[i]);
		for(auto p:v2[i]){
			for(int j=Q2[p].l;j<=Q2[p].r;j++){
				res[Q2[p].id][1]+=ask2(colo[j]);
			}
			// cerr<<Q2[p].id<<" "<<res[Q2[p].id][1]<<" ->1\n";
		}
	}
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1]+ask1(colo[i]);
		insert1(colo[i]);
		for(auto p:v1[i]){
			for(int j=Q1[p].l;j<=Q1[p].r;j++){
				res[Q1[p].id][0]+=ask1(colo[j]);
			}
			// cerr<<i<<" "<<Q1[p].l<<" "<<Q1[p].r<<" "<<Q1[p].id<<" "<<res[Q1[p].id][0]<<" <-1\n";
		}
	}
	l=2,r=1;
	int nowans=0;
	for(int i=1;i<=m;i++){
		// cout<<suf[Q[i].l]<<" "<<suf[l]<<" "<<pre[Q[i].r]<<" "<<pre[r]<<"\n";
		if(l<Q[i].l)nowans-=suf[l]-suf[Q[i].l]-res[i][0];
		else nowans+=suf[Q[i].l]-suf[l]-res[i][0];
		l=Q[i].l;
		if(r<Q[i].r)nowans+=pre[Q[i].r]-pre[r]-res[i][1];
		else nowans-=pre[r]-pre[Q[i].r]-res[i][1];
		r=Q[i].r;
		ans[Q[i].id]=nowans;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

P5501

考虑莫队拆贡献。举个例子，对于 $[l,r]\to[l,r+1]$，不难发现原来 $[l,r]$ 中比新数大的排名都向后移了一位，那么贡献就是 $[l,r]$ 区间内比 $a[r+1]$ 大的数的和再加上 $[l,r]$ 中比 $a[r+1]$ 小的数的个数加一再乘上 $a[r+1]$。

不难发现上面所提到的两个东西都能使用权值线段树维护，那么可以尝试使用二离来优化。

首先，对于第一种贡献，使用两个前缀和离线下来暴力扫描线 + 分块维护即可，和 P5047 差不多，但是支持两个前缀和做法。

对于第二种贡献，我们同样发现它是可差分的，那么令 $f(k,[l,r])$ 为 $[l,r]$ 中比 $k$ 小的数加一再乘上 $a[k]$，使用近乎一样的分块维护就行了。

这应该是最后一道莫队二离了，但是显然今天冲不出来了，开摆！

冲出来了。有一个比较重要的细节：注意推出来的式子中，前缀和有些被减去，有些是加上，这样注定需要让我们再记录一个前缀和，即颜色种类的前缀和，用于处理 II 类贡献的 加一。

// Problem: P5501 [LnOI2019] 来者不拒，去者不追
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5501
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-21 12:25:39
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int colo[500005];
const int maxc=1e5;
int base,B,C;
int belong[maxc+5],a1[maxc+5],k1[maxc+5],st[maxc+5],ed[maxc+5];//求严格大于的数的和-->后缀和
int a2[maxc+5],k2[maxc+5];//求严格小于的数的个数-->前缀和
void insert1(int x){
	int bx=belong[x];
	for(int i=1;i<=bx;i++)k1[i]+=x;
	for(int i=st[bx];i<=x;i++)a1[i]+=x;
	return;
}
int ask1(int x){
	int bx=belong[x];
	int res=k1[bx+1];
	int ext=0;
	if(x!=ed[bx])ext=a1[x+1];
	return res+ext;
}
void insert2(int x){
	int bx=belong[x];
	for(int i=bx;i<=C;i++)k2[i]++;
	for(int i=x;i<=ed[bx];i++)a2[i]++;
	return;
}
int ask2(int x){
	int bx=belong[x];
	int res=k2[bx-1];
	int ext=0;
	if(x!=st[bx])ext=a2[x-1];
	return res+ext;
}
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(((l/base)&1)?r>a.r:r<a.r):l<a.l;
	}
}Q[500001];
int ans[500001];
int res[500001][2];
int pre1[500001],pre2[500001],pre[500001];
struct qu2{
	int l,r,wh,id;
}Q2[1000001];
int q2cnt;
vector<int> v[500001];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>colo[i],pre[i]=pre[i-1]+colo[i];
	B=sqrt(maxc);
	C=maxc/B;
	for(int i=1;i<=C;i++){
		st[i]=(i-1)*B+1;
		ed[i]=i*B;
		for(int j=st[i];j<=ed[i];j++)belong[j]=i;
	}
	if(maxc%B){
		C++;
		st[C]=(C-1)*B+1;
		ed[C]=maxc;
		for(int j=st[C];j<=ed[C];j++)belong[j]=C;
	}
	base=n/sqrt(m);
	if(base==0)base=sqrt(n);
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1);
	int l=2,r=1;
	for(int i=1;i<=m;i++){
		if(l<Q[i].l)Q2[++q2cnt]={l,Q[i].l-1,0,i};
		else Q2[++q2cnt]={Q[i].l,l-1,0,i};
		l=Q[i].l;
		v[r].push_back(q2cnt);
		if(r<Q[i].r)Q2[++q2cnt]={r+1,Q[i].r,1,i};
		else Q2[++q2cnt]={Q[i].r+1,r,1,i};
		r=Q[i].r;
		v[l-1].push_back(q2cnt);
	}
	for(int i=1;i<=n;i++){
		pre1[i]=pre1[i-1]+ask1(colo[i])+ask2(colo[i])*colo[i];
		insert1(colo[i]);
		insert2(colo[i]);
		pre2[i]=pre2[i-1]+ask1(colo[i])+ask2(colo[i])*colo[i];
		for(auto p:v[i]){
			for(int j=Q2[p].l;j<=Q2[p].r;j++){
				res[Q2[p].id][Q2[p].wh]+=ask1(colo[j])+ask2(colo[j])*colo[j];
			}
			// cerr<<Q2[p].l<<" "<<Q2[p].r<<" "<<Q2[p].id<<" "<<Q2[p].wh<<" "<<res[Q2[p].id][Q2[p].wh]<<"\n";
		}
	}
	l=2,r=1;
	int nowans=0;
	for(int i=1;i<=m;i++){
		if(l<Q[i].l)nowans-=res[i][0]-(pre2[Q[i].l-1]-pre2[l-1])+pre[Q[i].l-1]-pre[l-1];
		else nowans+=res[i][0]-(pre2[l-1]-pre2[Q[i].l-1])+pre[l-1]-pre[Q[i].l-1];
		l=Q[i].l;
		if(r<Q[i].r)nowans+=(pre1[Q[i].r]-pre1[r])-res[i][1]+pre[Q[i].r]-pre[r];
		else nowans-=(pre1[r]-pre1[Q[i].r])-res[i][1]+pre[r]-pre[Q[i].r];
		r=Q[i].r;
		ans[Q[i].id]=nowans;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

带修莫队

高维莫队的一种，就是强行加了一维时间维变成查询一个三维点。

那么我们现在的单点 $[l,r,time]$ 就要 $O(1)$ 转移到 $[l-1,r,time],[l+1,r,time],[l,r-1,time],[l,r+1,time],[l,r,time+1],[l,r,time-1]$。

前面四个和普通莫队的做法一样，后面两个就模拟修改就行了。注意 $time+1,time-1$ 这两个修改正着和反着是不一样的，都需要存。

板子题

// Problem: P1903 [国家集训队] 数颜色 / 维护队列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1903
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// Start coding at 2023-12-22 09:55:11
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,base;
struct qu{
	int l,r,t,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(r/base==a.r/base?(((r/base)&1)?t>a.t:t<a.t):r<a.r):l<a.l;
	}
}Q[200001];
int ans[200001],colo[200001],a[200001];
int cnt[1000001],res;
int to[200001],from[200001],mdfp[200001];
void add(int x,bool k=1){
	if(k)x=colo[x];
	cnt[x]++;
	if(cnt[x]==1)res++;
	return;
}
void del(int x,bool k=1){
	if(k)x=colo[x];
	cnt[x]--;
	if(!cnt[x])res--;
	return;
}
void upd(int x,int l,int r,bool arr){
	if(arr){
		if(mdfp[x]>=l&&mdfp[x]<=r)del(from[x],0),add(to[x],0);
		colo[mdfp[x]]=to[x];
	}
	else{
		if(mdfp[x]>=l&&mdfp[x]<=r)del(to[x],0),add(from[x],0);
		colo[mdfp[x]]=from[x];
	}
	return;
}
int qcnt,x,y;
int main(){
	ios::sync_with_stdio(0);
	int tcnt=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>colo[i],a[i]=colo[i];
	char op;
	for(int i=1;i<=m;i++){
		cin>>op>>x>>y;
		if(op=='Q'){
			Q[++qcnt]={x,y,tcnt,qcnt};
		}else{
			from[tcnt]=a[x];
			to[tcnt]=y;
			mdfp[tcnt]=x;
			a[x]=y;
			tcnt++;
		}
	}
	base=pow(n,0.6666);
	sort(Q+1,Q+qcnt+1);
	int l=2,r=1,t=1;
	for(int i=1;i<=qcnt;i++){
		while(l!=Q[i].l||r!=Q[i].r){
			while(l<Q[i].l&&l<r)del(l++);
			while(l>Q[i].l)add(--l);
			while(r<Q[i].r)add(++r);
			while(r>Q[i].r&&l<r)del(r--);
		}
		while(t>Q[i].t)upd(--t,l,r,0);
		while(t<Q[i].t)upd(t++,l,r,1);
		ans[Q[i].id]=res;
	}
	for(int i=1;i<=qcnt;i++)cout<<ans[i]<<"\n";
	return 0;
}

感觉例题都是板子，感觉其实这个莫队是用来乱搞的。

一些经验：UVA12345，P2464。

回滚莫队

这种莫队用了一种很巧妙的思想来防止出现插入或删除其中一种情况的。

前提

• 建议使用该莫队前仔细想一想有没有能平衡复杂度的做法（如值域分块等）。
• 插入删除 $O(1)-(>O(1))$ 或 $(>O(1))-O(1)$。

思想

本处只讲不删莫队，不插入莫队本质相同。

考虑莫队上界复杂度很松是因为左右端点的移动次数严格跑不满，所以我们利用这个性质来微调左右端点的移动。

对于排序过后的每一块，采用分块的类似做法，考虑左右端点在同一块里面的直接进行暴力，此时复杂度为 $O(\sqrt n)$ 的。而对于左右端点不在同一块的，第一次莫队的转移不难发现一定是只插入的：

首先会转移到这样的地方，这个时候把这里所有的数组等状态记录下来。

这个时候移动 $l$ 指针，算出 $l$ 在块内时询问右端点为 $r$ 的所有询问的答案。然后不难发现如果这个时候出现一个类似于 $[ed,r'](r'>r)$ 的询问就直接爆炸了！这个时候就可以体现刚刚存的那个状态的重要性了。考虑直接把当前状态还原到我们刚刚记录的状态，不难发现其实这样是可以继续增加的。

看似解决了不能删除的问题，但是出现了新的问题，即不能很快速的清空。考虑每次最多移动 $O(\sqrt n)$ 次左端点，那么其实可以维护数组有哪些点被改变了，那么就可以直接进行还原。

板子题

板子题就是很板，分讨情况即可，至于 add，左移需要记录转移，右移需要更新如果左移，转移回来的所需最终信息。

// Problem: P5906 【模板】回滚莫队&不删除莫队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5906
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Start coding at 2023-12-23 10:16:32
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
int colo[200001],org[200001];
int base;
struct qu{
	int l,r,id;
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(r==a.r?l>a.l:r<a.r):l<a.l;
	}
}Q[200001];
int ans[200001];
int res;
int L[200001],R[200001];
int fromL[200001],fromR[200001],mdfp[200001],gol,gor,resed,fcnt;
int re2,l2[200001];
void add(int x,bool o){
	if(o){
		fromL[++fcnt]=L[colo[x]];
		fromR[fcnt]=R[colo[x]];
		mdfp[fcnt]=colo[x];
	}
	if(!L[colo[x]]&&!R[colo[x]]){
		L[colo[x]]=R[colo[x]]=x;
		// cerr<<"add "<<x<<" "<<colo[x]<<" "<<L[colo[x]]<<" "<<R[colo[x]]<<"\n";
		return;
	}
	if(L[colo[x]]>x){
		L[colo[x]]=x;
		res=max(res,R[colo[x]]-L[colo[x]]);
	}else{
		R[colo[x]]=x;
		res=max(res,R[colo[x]]-L[colo[x]]);
	}
	// cerr<<"add "<<x<<" "<<colo[x]<<" "<<L[colo[x]]<<" "<<R[colo[x]]<<"\n";
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>colo[i],org[i]=colo[i];
	sort(org+1,org+n+1);
	int ocnt=unique(org+1,org+n+1)-org-1;
	for(int i=1;i<=n;i++)colo[i]=lower_bound(org+1,org+ocnt+1,colo[i])-org;
	cin>>m;
	base=n/sqrt(m);
	if(base==0)base=sqrt(n);
	for(int i=1;i<=m;i++){
		cin>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	sort(Q+1,Q+m+1);
	int l=base,r=base-1,nowmax=base-1;
	gol=l,gor=r;
	for(int i=1;i<=m;i++){
		// cerr<<i<<" "<<Q[i].id<<" "<<Q[i].l<<" "<<Q[i].r<<" "<<l<<" "<<r<<"\n";
		if(l>Q[i].l&&(Q[i].r<=nowmax||Q[i].r==r)){
			// cerr<<"in 1\n";
			if(Q[i].r>nowmax){//|L...l'.....|....R...
				while(l>Q[i].l)add(--l,1);
				// assert(l==Q[i].l&&r==Q[i].r);
				ans[Q[i].id]=res;
			}else{//|L.......R....|l'
				// cerr<<"SPJ\n";
				re2=0;
				for(int o=Q[i].l;o<=Q[i].r;o++){
					if(!l2[colo[o]])l2[colo[o]]=o;
					else re2=max(re2,o-l2[colo[o]]);
				}
				for(int o=Q[i].l;o<=Q[i].r;o++)l2[colo[o]]=0;
				ans[Q[i].id]=re2;
			}
		}else if(Q[i].l<=nowmax){//|...l'......L....|....R...
			// cerr<<"in 2\n";
			for(int o=fcnt;o>=1;o--){
				L[mdfp[o]]=fromL[o];
				R[mdfp[o]]=fromR[o];
			}
			res=resed;
			l=gol,r=gor;
			fcnt=0;
			while(r<Q[i].r){
				add(++r,0);
				resed=res;
				++gor;
			}
			// cerr<<gor<<"\n";
			i--;
		}else{//|.....l'.....|.....L......R....
			// cerr<<"in 3\n";
			res=resed=0;
			nowmax+=base;
			// if(nowmax>=n)nowmax=n;
			gol=l=nowmax+1,gor=r=nowmax;
			fcnt=0;
			for(int o=1;o<=ocnt;o++)L[o]=R[o]=0;
			i--;
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}

例题

P5386 数字游戏

莫队目前的最后一题，后面的题当做练习题有空再做。

这道题的后半部分是第十分块的后半部分，所以感觉非常恶心。首先考虑用莫队跑值域区间，把符合条件的数记录为 $1$，不符合条件的数记录为 $0$，由于是排列，记录次数为 $O(n\sqrt m)$ 的，这样我们就需要维护一个 $O(1)-O(\sqrt n)$ 的数据结构来维护区间极长连续 $1$ 区间的长度。

考虑序列分块，对于每个 $1$ 连续段的开头和结尾记录下其结尾和开头的位置，对于修改为 $1$，考虑暴力找到左右两边的值进行合并答案，对于修改为 $0$，发现对于区间的分裂不好维护，用回滚莫队处理即可；对于询问，整块统计答案，块与块之间可以 $O(1)$ 合并，散块暴力遍历即可。

总时间复杂度为 $O(n\sqrt m+m\sqrt n)$。

我实现的常数巨大…

// Problem: P5386 [Cnoi2019] 数字游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5386
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Start coding at 2023-12-25 09:23:47
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,pl[200005],colo[200005];
int B,base,C,belong[200005];
int st[200005],ed[200005];
int fromst1[1000005],fromed1[1000005],frombloans[1000005],fromnum[1000005],mdfp[1000005],fcnt,gol,gor;
int tempst1[200005],temped1[200005],tempbloans[200005],tempnum[200005];
struct qu{
	int L,R,l,r,id;//LR->sequence lr->value
	bool operator < (const qu &a) const{
		return l/base==a.l/base?(r==a.r?l>a.l:r<a.r):l<a.l;
	}
}Q[200005];
int ans[200005];
int geta(int l,int r,int mp){
	if(l>r)return 0;
	return mp*((r-l+1)*(r-l)/2+r-l+1);
}
int geta(int len,int mp){
	return mp*((len)*(len-1)/2+len);
}
int getans(int* st1,int* ed1,int* bloans,int* num,int l,int r){
	int bl=belong[l],br=belong[r],res=0,lastl=0,lastr=0;
	// for(int i=1;i<=n;i++)cout<<st1[i]<<" ";
	// cout<<"\n";
	// for(int i=1;i<=n;i++)cout<<ed1[i]<<" ";
	// cout<<"\n";
	if(bl==br){
		// cerr<<1<<"\n";
		int lst=0;
		for(int i=l;i<=r;i++){
			// cout<<num[i]<<"\n";
			if(!num[i]){
				if(lst!=0)res+=geta(lst,i-1,1),lst=0;
			}
			else{
				if(lst==0)lst=i;
			}
		}
		if(lst!=0)res+=geta(lst,r,1);
		return res;
	}
	for(int i=ed[bl];i>=l;i--){
		if(st1[i]){
			int red=max(l,st1[i]);
			res+=geta(red,i,1),i=red;
		}
	}
	// cout<<res<<" in1\n";
	for(int i=st[br];i<=r;i++){
		if(ed1[i]){
			int red=min(r,ed1[i]);
			res+=geta(i,red,1),i=red;
		}
	}
	// cout<<res<<" in2\n";
	for(int i=bl+1;i<=br-1;i++)res+=bloans[i];
	// cout<<res<<" in2\n";
	lastr=ed[bl];
	if(st1[ed[bl]])lastl=max(l,st1[ed[bl]]);
	else lastl=lastr+1;
	res-=geta(lastl,lastr,1);
	// cout<<lastl<<" "<<lastr<<" 0\n";
	for(int i=bl+1;i<=br-1;i++){
		if(ed1[st[i]]==ed[i]){
			res-=geta(st[i],ed[i],1);
			lastr=ed[i];
		}
		else{
			if(ed1[st[i]]!=0){
				res-=geta(st[i],ed1[st[i]],1);
				lastr=ed1[st[i]];
			}
			res+=geta(lastl,lastr,1);
			lastr=ed[i];
			if(st1[ed[i]])lastl=st1[ed[i]];
			else lastl=ed[i]+1;
			res-=geta(lastl,lastr,1);
		}
	}
	if(ed1[st[br]]){
		int red=min(ed1[st[br]],r);
		res-=geta(st[br],red,1);
		lastr=red;
	}
	// cerr<<lastl<<" "<<lastr<<"\n";
	res+=geta(lastl,lastr,1);
	return res;
}
int st1[200005],ed1[200005],bloans[200005],num[200005];
void record(int pl){
	mdfp[++fcnt]=pl;
	fromst1[fcnt]=st1[pl];
	fromed1[fcnt]=ed1[pl];
	fromnum[fcnt]=num[pl];
	frombloans[fcnt]=bloans[belong[pl]];
	return;
}
void merge(int r,int id,bool o){
	int l=r-1;
	if(st1[l]&&ed1[r]){
		if(o){
			record(st1[l]);
			record(ed1[r]);
			record(l);
			record(r);
		}
		int ll=st1[l],rr=ed1[r];
		bloans[id]+=geta(r,ed1[r],-1);
		bloans[id]+=geta(st1[l],l,-1);
		st1[ed1[r]]=st1[l],ed1[st1[l]]=ed1[r];
		st1[l]=ed1[r]=0;
		bloans[id]+=geta(ll,rr,1);
	}
	return;
}
void mdf(int x,bool o){
	//CHANGE 0/1[x](0)->1
	if(o)record(x);
	st1[x]=ed1[x]=x;
	num[x]=1;
	bloans[belong[x]]++;
	if(belong[x-1]==belong[x])merge(x,belong[x],o);
	if(belong[x]==belong[x+1])merge(x+1,belong[x],o);
	return;
}
void merge2(int r,int id){
	int l=r-1;
	if(tempst1[l]&&temped1[r]){
		int ll=tempst1[l],rr=temped1[r];
		tempbloans[id]+=geta(r,temped1[r],-1);
		tempbloans[id]+=geta(tempst1[l],l,-1);
		tempst1[temped1[r]]=tempst1[l],temped1[tempst1[l]]=temped1[r];
		tempst1[l]=temped1[r]=0;
		tempbloans[id]+=geta(ll,rr,1);
	}
	return;
}
void mdf2(int x){
	//CHANGE 0/1[x](0)->1
	tempst1[x]=temped1[x]=x;
	tempnum[x]=1;
	tempbloans[belong[x]]++;
	if(belong[x-1]==belong[x])merge2(x,belong[x]);
	if(belong[x]==belong[x+1])merge2(x+1,belong[x]);
	return;
}
void clear2(int x){
	tempst1[x]=temped1[x]=tempnum[x]=0;
	tempbloans[belong[x]]=0;
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>colo[i],pl[colo[i]]=i;
	B=sqrt(n);
	C=n/B;
	base=n/sqrt(q);
	if(base==0)base=sqrt(n);
	for(int i=1;i<=C;i++){
		st[i]=(i-1)*B+1;
		ed[i]=i*B;
		for(int j=st[i];j<=ed[i];j++)belong[j]=i;
	}
	if(n%B){
		C++;
		st[C]=(C-1)*B+1;
		ed[C]=n;
		for(int j=st[C];j<=ed[C];j++)belong[j]=C;
	}
	for(int i=1;i<=q;i++){
		cin>>Q[i].L>>Q[i].R>>Q[i].l>>Q[i].r;
		Q[i].id=i;
	}
	// mdf(2,0),mdf(3,0),mdf(4,0);
	// cout<<getans(st1,ed1,bloans,1,4)<<"\n";
	sort(Q+1,Q+q+1);
	int l=base,r=base-1,nowmax=base-1;
	gol=l,gor=r;
	for(int i=1;i<=q;i++){
		if(l>Q[i].l&&(r==Q[i].r||Q[i].r<=nowmax)){
			//|..L.l'...|....R
			//|..L..R...|....
			if(Q[i].r<=nowmax){
				//bf
				for(int p=Q[i].l;p<=Q[i].r;p++)mdf2(pl[p]);
				ans[Q[i].id]=getans(tempst1,temped1,tempbloans,tempnum,Q[i].L,Q[i].R);
				for(int p=Q[i].l;p<=Q[i].r;p++)clear2(pl[p]);
			}else{
				//getans
				while(l>Q[i].l)mdf(pl[--l],1);
				// cerr<<l<<" "<<r<<" "<<Q[i].l<<" "<<Q[i].r<<"\n";
				// assert(r==Q[i].r&&l==Q[i].l);
				ans[Q[i].id]=getans(st1,ed1,bloans,num,Q[i].L,Q[i].R);
			}
		}else if(Q[i].l<=nowmax){
			//|..l'...L.|..R....
			for(int p=fcnt;p>=1;p--){
				bloans[belong[mdfp[p]]]=frombloans[p];
				st1[mdfp[p]]=fromst1[p];
				ed1[mdfp[p]]=fromed1[p];
				num[mdfp[p]]=fromnum[p];
			}
			l=gol,r=gor;
			fcnt=0;
			while(r<Q[i].r)mdf(pl[++r],0),++gor;
			i--;
		}else{
			//|...l'....|...L...R..
			nowmax+=base;
			fcnt=0;
			for(int i=1;i<=n;i++)bloans[i]=st1[i]=ed1[i]=num[i]=0;
			gol=l=nowmax+1;
			gor=r=nowmax;
			i--;
		}
		// assert(i<=100);
	}
	// mdf2(2),mdf2(5),mdf2(7),mdf2(9),mdf2(10);
	// cout<<getans(tempst1,temped1,tempbloans,1,16)<<"\n";
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}

5k 代码/jk…