登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.9 分块与莫队 › 分块与莫队 / 搜索
JSON MD

2.9 分块与莫队

1.区修,单查 optimize
38 行
CPP JSON
【1.区修,单查】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void change(Re l,Re r,Re x) — 核心算法函数 LL ask(Re x) — 核心算法函数 关键配置: N=5e4+3,T=230 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 37 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
	Re p=pt[l],q=pt[r];
	if(p==q){F(i,l,r)a[i]+=x;S[p]+=x*(r-l+1);}
	else{
		F(i,p+1,q-1)add[i]+=x;
		F(i,l,R[p])a[i]+=x;S[p]+=x*(R[p]-l+1);
		F(i,L[q],r)a[i]+=x;S[q]+=x*(r-L[q]+1);
	}
}
inline LL ask(Re x){return a[x]+add[pt[x]];}
int main(){
	in(n),t=sqrt(Q=n);
	F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
	F(i,1,n)in(x),a[i]=x;
	F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
	while(Q--){
		in(n),in(l),in(r),in(x);
		if(n)printf("%lld\n",ask(r));
		else change(l,r,x);
	}
}
2.区修,区查 小于c2的个数
51 行
CPP JSON
【2.区修,区查(小于c2的个数)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void sak(Re l,Re r,Re p,Re x) — 后缀数组 void change(Re l,Re r,Re x) — 核心算法函数 LL ask(Re l,Re r,LL x) — 核心算法函数 关键配置: N=5e4+3,T=230 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 50 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define lo(l,r,x) (lower_bound(b+l,b+r+1,x)-b)
using namespace std;
const int N=5e4+3,T=230;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T];LL a[N],b[N],add[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
	Re p=pt[l],q=pt[r];
	if(p==q)sak(l,r,p,x);
	else{
		F(i,p+1,q-1)add[i]+=x;
		sak(l,R[p],p,x),sak(L[q],r,q,x);
	}
}
inline LL ask(Re l,Re r,LL x){
	Re p=pt[l],q=pt[r];LL ans=0;
	if(p==q){F(i,l,r)ans+=a[i]+add[p]<x;return ans;}
	else{
		F(i,p+1,q-1)ans+=lo(L[i],R[i],x-add[i])-L[i];
		F(i,l,R[p])ans+=a[i]+add[p]<x;
		F(i,L[q],r)ans+=a[i]+add[q]<x;
	}
	return ans;
}
int main(){
	in(n),t=sqrt(Q=n);
	F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
	F(i,1,n)in(x),a[i]=b[i]=x;
	F(i,1,t)F(j,L[i],R[i])pt[j]=i;
	F(i,1,t)sort(b+L[i],b+R[i]+1);
	while(Q--){
		in(o),in(l),in(r),in(x);
		if(o)printf("%lld\n",ask(l,r,(LL)x*x));
		else change(l,r,x);
	}
}
3.区修,区查 x的前驱
50 行
CPP JSON
【3.区修,区查(x的前驱)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void sak(Re l,Re r,Re p,Re x) — 后缀数组 void change(Re l,Re r,Re x) — 核心算法函数 int ask(Re l,Re r,Re x) — 核心算法函数 关键配置: N=1e5+3,T=330 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 49 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf -2147483647
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T],a[N],b[N],add[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
    Re p=pt[l],q=pt[r];
    if(p==q)sak(l,r,p,x);
    else{
        F(i,p+1,q-1)add[i]+=x;
        sak(l,R[p],p,x),sak(L[q],r,q,x);
    }
}
inline int ask(Re l,Re r,Re x){
    Re p=pt[l],q=pt[r],ans=inf,w;
    if(p==q){F(i,l,r)if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);}
    else{
        F(i,p+1,q-1)w=lower_bound(b+L[i],b+R[i]+1,x-add[i])-(b+1),ans=w>=L[i]?max(ans,b[w]+add[i]):ans;
        F(i,l,R[p])if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);
        F(i,L[q],r)if(a[i]+add[q]<x)ans=max(ans,a[i]+add[q]);
    }
    return ans==inf?-1:ans;
}
int main(){
    in(n),t=sqrt(Q=n);
    F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
    F(i,1,n)in(x),a[i]=b[i]=x;
    F(i,1,t)F(j,L[i],R[i])pt[j]=i;
    F(i,1,t)sort(b+L[i],b+R[i]+1);
    while(Q--){
        in(o),in(l),in(r),in(x);
        if(o)printf("%d\n",ask(l,r,x));
        else change(l,r,x);
    }
}
4.区修,区查 Sum
47 行
CPP JSON
【4.区修,区查(Sum)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void change(Re l,Re r,Re x) — 核心算法函数 LL ask(Re l,Re r) — 核心算法函数 关键配置: N=5e4+3,T=230 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 46 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
	Re p=pt[l],q=pt[r];
	if(p==q){F(i,l,r)a[i]+=x;S[p]+=(LL)x*(r-l+1);}
	else{
		F(i,p+1,q-1)add[i]+=x;
		F(i,l,R[p])a[i]+=x;S[p]+=(LL)x*(R[p]-l+1);
		F(i,L[q],r)a[i]+=x;S[q]+=(LL)x*(r-L[q]+1);
	}
}
inline LL ask(Re l,Re r){
	Re p=pt[l],q=pt[r];LL ans=0;
	if(p==q){F(i,l,r)ans+=a[i];ans+=add[p]*(r-l+1);}
	else{
		F(i,p+1,q-1)ans+=S[i]+add[i]*(LL)(R[i]-L[i]+1);
		F(i,l,R[p])ans+=a[i];ans+=add[p]*(LL)(R[p]-l+1);
		F(i,L[q],r)ans+=a[i];ans+=add[q]*(LL)(r-L[q]+1);
	}
	return ans;
}
int main(){
	in(n),t=sqrt(Q=n);
	F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
	F(i,1,n)in(x),a[i]=x;
	F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
	while(Q--){
		in(n),in(l),in(r),in(x);
		if(n)printf("%lld\n",ask(l,r)%(x+1));
		else change(l,r,x);
	}
}
5.区修,区查(Sum) Sqrt
51 行
CPP JSON
【5.区修,区查(Sum)(Sqrt)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void sakura(Re p) — 后缀数组 void change(Re l,Re r) — 核心算法函数 LL ask(Re l,Re r) — 核心算法函数 关键配置: N=5e4+3,T=230 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 50 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],pan[T];LL a[N],S[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void sakura(Re p){
	if(pan[p])return;pan[p]=1,S[p]=0;
	F(i,L[p],R[p])S[p]+=(a[i]=sqrt(a[i])),pan[p]&=(a[i]<=1);
}
inline void change(Re l,Re r){
	Re p=pt[l],q=pt[r];
	if(p==q){F(i,l,r)S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];}
	else{
		F(i,p+1,q-1)sakura(i);
		F(i,l,R[p])S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];
		F(i,L[q],r)S[q]-=a[i],a[i]=sqrt(a[i]),S[q]+=a[i];
	}
}
inline LL ask(Re l,Re r){
	Re p=pt[l],q=pt[r];LL ans=0;
	if(p==q){F(i,l,r)ans+=a[i];}
	else{
		F(i,p+1,q-1)ans+=S[i];
		F(i,l,R[p])ans+=a[i];
		F(i,L[q],r)ans+=a[i];
	}
	return ans;
}
int main(){
	in(n),t=sqrt(Q=n);
	F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
	F(i,1,n)in(x),a[i]=x;
	F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
	while(Q--){
		in(n),in(l),in(r),in(x);
		if(n)printf("%lld\n",ask(l,r));
		else change(l,r);
	}
}
6.单插,单查 w前面插入x
39 行
CPP JSON
【6.单插,单查(w前面插入x)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void change(Re w,Re x) — 核心算法函数 int ask(Re w) — 核心算法函数 F(i,1,t) — 核心算法函数 关键配置: N=1e5+3,T=330 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 38 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<vector>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,o,t,x,l,r,Q,fu,pt[N],pw[N],L[T],R[T];
vector<int>a[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void change(Re w,Re x){
    F(i,1,t)
        if(w>a[i].size())w-=a[i].size();
        else{a[i].insert(a[i].begin()+w-1,x);return;}
}
inline int ask(Re w){
    F(i,1,t)
        if(w>a[i].size())w-=a[i].size();
        else return a[i][w-1];
}
int main(){
    in(n),t=sqrt(Q=n);
    F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
    F(i,1,t){F(j,L[i],R[i])in(x),a[i].push_back(x),pt[j]=i;}
    while(Q--){
        in(o),in(l),in(r),in(x);
        if(o)printf("%d\n",ask(r));
        else change(l,r);
    }
}
7.区修,单查 +,×
52 行
CPP JSON
【7.区修,单查(+,×)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void spread(Re p) — 预处理函数 void change(Re l,Re r,Re x) — 核心算法函数 void change2(Re l,Re r,Re x) — 核心算法函数 int ask(Re x) — 核心算法函数 关键配置: N=1e5+3,T=320 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 51 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=320;
int n,t,x,l,r,Q,fu,P=10007,pt[N],L[T],R[T],a[N],add[T],mul[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void spread(Re p){
	F(i,L[p],R[p])(((a[i]*=mul[p])%=P)+=add[p])%=P;
	add[p]=0,mul[p]=1;
}
inline void change(Re l,Re r,Re x){
	Re p=pt[l],q=pt[r];spread(p);
	if(p==q)F(i,l,r)(a[i]+=x)%=P;
	else{
		spread(q);
		F(i,p+1,q-1)(add[i]+=x)%P;
		F(i,l,R[p])(a[i]+=x)%=P;
		F(i,L[q],r)(a[i]+=x)%=P;
	}
}
inline void change2(Re l,Re r,Re x){
	Re p=pt[l],q=pt[r];spread(p);
	if(p==q)F(i,l,r)(a[i]*=x)%=P;
	else{
		spread(q);
		F(i,p+1,q-1)(add[i]*=x)%=P,(mul[i]*=x)%=P;
		F(i,l,R[p])(a[i]*=x)%=P;
		F(i,L[q],r)(a[i]*=x)%=P;
	}
}
inline int ask(Re x){return (a[x]*mul[pt[x]]%P+add[pt[x]])%P;}
int main(){
	in(n),t=sqrt(Q=n);
	F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t,mul[i]=1;
	if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1,mul[t]=1;
	F(i,1,n)in(a[i]);
	F(i,1,t)F(j,L[i],R[i])pt[j]=i;
	while(Q--){
		in(n),in(l),in(r),in(x);
		if(n>1)printf("%d\n",ask(r));
		else n?change2(l,r,x%P):change(l,r,x%P);
	}
}
8.区修,区查(c的个数) 推平
96 行
CPP JSON
【8.区修,区查(c的个数)(推平)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 int sak(Re l,Re r,Re p,Re x) — 后缀数组 int fuck(Re p,Re x) — 核心算法函数 int sovle(Re l,Re r,Re x) — 核心算法函数 F(i,1,t) — 核心算法函数 关键配置: N=1e5+3,T=330 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 95 行 CPP
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=330;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],a[N],tag[T];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int sak(Re l,Re r,Re p,Re x){
    Re tmp=0;
    if(tag[p]!=-1){F(i,L[p],R[p])a[i]=tag[p];tmp+=(r-l+1)*(tag[p]==x);}
    else F(i,l,r)tmp+=a[i]==x;
    tag[p]=-1;F(i,l,r)a[i]=x;
    return tmp;
}
inline int fuck(Re p,Re x){
    Re tmp=0;
    if(tag[p]!=-1){F(j,L[p],R[p])a[j]=tag[p];tmp+=(R[p]-L[p]+1)*(tag[p]==x);}
    else F(j,L[p],R[p])tmp+=a[j]==x;
    tag[p]=x;
    return tmp;
}
inline int sovle(Re l,Re r,Re x){
    Re p=pt[l],q=pt[r],ans=0;
    if(p==q)return l==r?fuck(p,x):sak(l,r,p,x);
    else{
        F(i,p+1,q-1)ans+=fuck(i,x);
        ans+=sak(l,R[p],p,x)+sak(L[q],r,q,x);
    }
    return ans;
}
int main(){
    in(n),t=sqrt(Q=n);
    F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
    F(i,1,n)in(x),a[i]=x;
    F(i,1,t){tag[i]=-1;F(j,L[i],R[i])pt[j]=i;}
    while(Q--){
        in(l),in(r),in(x);
        printf("%d\n",sovle(l,r,x));
    }
}
回滚莫队 歴史の研究
58 行
CPP JSON
【回滚莫队(歴史の研究)】 莫队算法(Mo's Algorithm)模板,通过离线排序优化区间查询。 核心函数: void in(Re &x) — 核心算法函数 核心结构体:Query 关键配置: N=1e5+3,M=1e5+3 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度 说明:freopen("123.txt","r",stdin);
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3;
int n,m,T,BL,BLN,A[N],b[N],Li[325],Ri[325],cnt[N],cnt_[N],belong[N];LL Ans[M];
struct Query{
	int l,r,id;
	inline bool operator<(const Query &O)const{
		Re B1=belong[l],B2=belong[O.l];
		return B1!=B2?B1<B2:r<O.r;
	}
}Q[M];
inline void in(Re &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),BL=sqrt(n)+1,BLN=n/BL+1;
	for(Re i=1;i<=BLN;++i){
		Li[i]=(i-1)*BL+1,Ri[i]=min(i*BL,n);
		for(Re j=Li[i];j<=Ri[i];++j)belong[j]=i;
	}
	for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
	sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
	for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
	for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
	sort(Q+1,Q+T+1);Re i=1;
	for(Re p=1;p<=BLN;++p){
		Re nowL=Ri[p]+1,nowR=Ri[p];LL ans=0;
		memset(cnt,0,sizeof(cnt));
		while(belong[Q[i].l]==p){
			Re L=Q[i].l,R=Q[i].r;
			if(belong[L]==belong[R]){
				LL tmp=0;
				for(Re j=L;j<=R;++j)cnt_[A[j]]=0;
				for(Re j=L;j<=R;++j)++cnt_[A[j]],tmp=max(tmp,(LL)b[A[j]]*cnt_[A[j]]);
				Ans[Q[i].id]=tmp;
			}
			else{
				while(nowR<R)cnt[A[++nowR]]++,ans=max(ans,(LL)b[A[nowR]]*cnt[A[nowR]]);
				LL tmp=ans;
				while(nowL>L)cnt[A[--nowL]]++,tmp=max(tmp,(LL)b[A[nowL]]*cnt[A[nowL]]);
				Ans[Q[i].id]=tmp;
				while(nowL<Ri[p]+1)--cnt[A[nowL++]];
			}
			++i;
		}
	}
	for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
带修莫队 数颜色/维护队列
56 行
CPP JSON
【带修莫队(数颜色/维护队列)】 莫队算法(Mo's Algorithm)模板,通过离线排序优化区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x) — 加法更新 void del(Re x) — 核心算法函数 核心结构体:Query, Change 关键配置: N=2e5+3,M=2e5+3,INF=1e6+3 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=2e5+3,M=2e5+3,INF=1e6+3;
int n,x,y,T,TQ,TC,BL,ans,a[N],Ans[M],cnt[INF];char op;
struct Query{
    int l,r,id,time;
    inline bool operator<(const Query &O)const{
        Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
        return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
    }
}Q[N];
struct Change{int w,co;}C[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(T),BL=pow(n,2.0/3.0);
    for(Re i=1;i<=n;++i)in(a[i]);
    for(Re i=1;i<=T;++i){
    	scanf(" %c",&op);
    	in(x),in(y);
    	if(op=='Q')++TQ,Q[TQ]=(Query){x,y,TQ,TC};
    	else C[++TC]=(Change){x,y};
	}
    sort(Q+1,Q+TQ+1);
    Re nowL=1,nowR=0,nowT=0;
    for(Re i=1;i<=TQ;++i){
        while(nowL<Q[i].l)del(a[nowL++]);
        while(nowL>Q[i].l)add(a[--nowL]);
        while(nowR>Q[i].r)del(a[nowR--]);
        while(nowR<Q[i].r)add(a[++nowR]);
        while(nowT<Q[i].time){
        	Re w=C[++nowT].w;
        	if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
        	swap(a[w],C[nowT].co);
		}
		while(nowT>Q[i].time){
			Re w=C[nowT].w;
        	if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
        	swap(a[w],C[nowT--].co);
		}
        Ans[Q[i].id]=ans;
    }
    for(Re i=1;i<=TQ;++i)printf("%d\n",Ans[i]);
}
树上带修莫队 糖果公园
90 行
CPP JSON
【树上带修莫队(糖果公园)】 莫队算法(Mo's Algorithm)模板,通过离线排序优化区间查询。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void change(Re x) — 核心算法函数 核心结构体:QAQ, LCA, Query, Change 关键配置: N=1e5+3,M=1e5+3,logN=17 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 89 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3,logN=17;
int n,m,x,y,o,T,op,id_O,A[N],V[N],W[N],B[N],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct LCA{
	int deep[N],ant[N][20];
	inline void dfs(Re x,Re fa){
		first[B[++B[0]]=x]=++id_O;
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
		last[B[++B[0]]=x]=++id_O;
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
		if(x==y)return x;
		for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T1;
int BL,TQ,TC,vis[N],cnt[N];LL ans,Ans[M];
struct Query{
	int l,r,id,lca,time;
	inline bool operator<(const Query &O)const{
		Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
		return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
	}
}Q[M];
struct Change{int w,co;}C[M];
inline void change(Re x){
	vis[x]?ans-=(LL)V[A[x]]*W[cnt[A[x]]--]:ans+=(LL)V[A[x]]*W[++cnt[A[x]]],vis[x]^=1;
}
int main(){
	freopen("123.txt","r",stdin);
	in(n),in(m),in(T),BL=pow(n<<1,2.0/3.0);
	for(Re i=1;i<=m;++i)in(V[i]);
	for(Re i=1;i<=n;++i)in(W[i]);
	for(Re i=1;i<n;++i)in(x),in(y),add(x,y),add(y,x);
	for(Re i=1;i<=n;++i)in(A[i]);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i){
		in(op),in(x),in(y);
		if(op){
			Re lca=T1.lca(x,y);
			if(first[x]>first[y])swap(x,y);
			if(lca==x)++TQ,Q[TQ]=(Query){first[x],first[y],TQ,0,TC};
			else ++TQ,Q[TQ]=(Query){last[x],first[y],TQ,lca,TC};
		}
		else C[++TC]=(Change){x,y};
	}
	sort(Q+1,Q+TQ+1);
	Re nowL=1,nowR=0,nowT=0;
	for(Re i=1;i<=TQ;++i){
		Re L=Q[i].l,R=Q[i].r,T=Q[i].time,lca=Q[i].lca;
		while(nowL<L)change(B[nowL++]);
		while(nowL>L)change(B[--nowL]);
		while(nowR>R)change(B[nowR--]);
		while(nowR<R)change(B[++nowR]);
		while(nowT<T){
			Re w=C[++nowT].w;
			if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
			else swap(A[w],C[nowT].co);
		}
		while(nowT>T){
			Re w=C[nowT].w;
			if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
			else swap(A[w],C[nowT].co);
			--nowT;
		}
		if(lca)change(lca);
		Ans[Q[i].id]=ans;
		if(lca)change(lca);
	}
	for(Re i=1;i<=TQ;++i)printf("%lld\n",Ans[i]);
}
树上静态莫队 Count on a tree II
74 行
CPP JSON
【树上静态莫队(Count on a tree II)】 莫队算法(Mo's Algorithm)模板,通过离线排序优化区间查询。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 void change(Re x) — 核心算法函数 核心结构体:QAQ, LCA, Query 关键配置: N=4e4+3,M=1e5+3,INF=1e6+3,logN=16 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度 说明:freopen("123.txt","r",stdin);
C++ 73 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,M=1e5+3,INF=1e6+3,logN=16;
int n,m,o,x,y,T,BL,id_O,b[N],A[N],B[N<<1],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct LCA{
	int deep[N],ant[N][20];
	inline void dfs(Re x,Re fa){
		first[B[++B[0]]=x]=++id_O;
		deep[x]=deep[ant[x][0]=fa]+1;
		for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
		for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
		last[B[++B[0]]=x]=++id_O;
	}
	inline int lca(Re x,Re y){
		if(deep[x]<deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
		if(x==y)return x;
		for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
}T1;
struct Query{
	int l,r,id,lca;
	inline bool operator<(const Query &O)const{
		Re B1=l/BL,B2=O.l/BL;
		return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
	}
}Q[M];
int ans,vis[N<<1],Ans[M],cnt[INF];
inline void change(Re x){
	vis[x]?ans-=!--cnt[A[x]]:ans+=!cnt[A[x]]++,vis[x]^=1;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),BL=sqrt(n<<1);
	for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
	sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
	for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
	m=n-1;while(m--)in(x),in(y),add(x,y),add(y,x);
	T1.dfs(1,0);
	for(Re i=1;i<=T;++i){
		in(x),in(y);Re lca=T1.lca(x,y);
		if(first[x]>first[y])swap(x,y);
		if(lca==x)Q[i]=(Query){first[x],first[y],i,0};
		else Q[i]=(Query){last[x],first[y],i,lca};
	}
	sort(Q+1,Q+T+1);
	Re nowL=1,nowR=0;
	for(Re i=1;i<=T;++i){
		Re L=Q[i].l,R=Q[i].r,lca=Q[i].lca;
		while(nowL<L)change(B[nowL++]);
		while(nowL>L)change(B[--nowL]);
		while(nowR>R)change(B[nowR--]);
		while(nowR<R)change(B[++nowR]);
		if(lca)change(lca);
		Ans[Q[i].id]=ans;
		if(lca)change(lca);
	}
	for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
静态莫队 D-query
40 行
CPP JSON
【静态莫队(D-query)】 莫队算法(Mo's Algorithm)模板,通过离线排序优化区间查询。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x) — 加法更新 void del(Re x) — 核心算法函数 核心结构体:Query 关键配置: N=3e4+3,M=2e5+3 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=3e4+3,M=2e5+3;
int n,T,BL,ans,A[N],cnt[1000003],Ans[M];
struct Query{
    int l,r,id;
    inline bool operator<(const Query &O)const{
        Re B1=l/BL,B2=O.l/BL;
        return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
    }
}Q[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
    in(n),BL=sqrt(n)+1;
    for(Re i=1;i<=n;++i)in(A[i]);
    in(T);
    for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
    sort(Q+1,Q+T+1);Re nowL=1,nowR=0;
    for(Re i=1;i<=T;++i){
        while(nowR<Q[i].r)add(A[++nowR]);
        while(nowR>Q[i].r)del(A[nowR--]);
        while(nowL>Q[i].l)add(A[--nowL]);
        while(nowL<Q[i].l)del(A[nowL++]);
        Ans[Q[i].id]=ans;
    }
    for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
小Z的袜子 optimize
41 行
CPP JSON
【小Z的袜子】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void in(Re &x) — 核心算法函数 void sakura(Re p,Re x) — 后缀数组 bool cmp(QAQ a,QAQ b) — 核心算法函数 LL gcd_(LL a,LL b) — 最大公约数 核心结构体:QAQ 关键配置: N=5e4+3 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 40 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define LL long long
using std::sort;
const int N=5e4+3;
int n,q,t,L,R,ip,fu,len,gs[N],pt[N],co[N];LL ans,gcd,fz[N],fm[N];
struct QAQ{int l,r,id;}Q[N];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void sakura(Re p,Re x){ans-=(LL)gs[fu=co[p]]*gs[fu],gs[fu]+=x,ans+=(LL)gs[fu]*gs[fu];} 
inline bool cmp(QAQ a,QAQ b){return pt[a.l]==pt[b.l]?a.r<b.r:a.l<b.l;}
inline LL gcd_(LL a,LL b){while(b^=a^=b^=a%=b);return a;}
int main(){
	in(n),in(q),t=sqrt(n);
	F(i,1,n)in(co[i]),pt[i]=i/t+1;
	F(i,1,q)in(Q[i].l),in(Q[i].r),Q[i].id=i;
	sort(Q+1,Q+q+1,cmp);
	L=1,R=0;
	F(i,1,q){
		while(L<Q[i].l)sakura(L++,-1);
		while(L>Q[i].l)sakura(--L,1);
		while(R<Q[i].r)sakura(++R,1);
		while(R>Q[i].r)sakura(R--,-1);
		ip=Q[i].id;
		if(Q[i].l==Q[i].r){fz[ip]=0,fm[ip]=1;continue;}
		fz[ip]=ans-(len=Q[i].r-Q[i].l+1);
		fm[ip]=(LL)len*(len-1);
		gcd=gcd_(fz[ip],fm[ip]),fz[ip]/=gcd,fm[ip]/=gcd;
	}
	F(i,1,q)printf("%lld/%lld\n",fz[i],fm[i]);
}
蒲公英参考程序 区间众数
73 行
CPP JSON
【蒲公英参考程序(区间众数)】 分块(Sqrt Decomposition)模板,将序列分成 sqrt(N) 块进行批量处理。 核心函数: void prework(无参数) — 预处理函数 void update(int i) — 单点/区间更新操作 int solve(int x,int y) — 主解题函数 复杂度:O((N+Q)·sqrt(N)) 或类似分块复杂度
C++ 72 行 CPP
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int u=40010;
int c[40][40][u],f[40][40],d[40][40],a[u],b[u],fa[u],fb[u],st[40],ed[40];
int n,m,t,l,tot,i,j,k,x,y,ans,L,R,cnt,num;

void prework()
{
	t=(int)pow(n*1.0,1.0/3);
	if(t) l=n/t;
	for(i=1;i<=t;i++) st[i]=(i-1)*l+1,ed[i]=i*l;
	if(ed[t]<n) st[t+1]=ed[t]+1,ed[++t]=n;
	memcpy(fa,a,sizeof(a));
	sort(fa+1,fa+n+1);
	for(i=1;i<=n;i++)
		if(i==1||fa[i]!=fa[i-1]) fb[++tot]=fa[i];
	for(i=1;i<=n;i++) b[i]=lower_bound(fb+1,fb+tot+1,a[i])-fb;
	for(i=1;i<=t;i++)
		for(j=i;j<=t;j++)
		{
			for(k=st[i];k<=ed[j];k++) c[i][j][b[k]]++;
			for(k=1;k<=tot;k++)
				if(c[i][j][k]>f[i][j]||c[i][j][k]==f[i][j]&&k<d[i][j])
					f[i][j]=c[i][j][k],d[i][j]=k;
		}
}

inline void update(int i)
{
	c[L][R][b[i]]++;
	if(c[L][R][b[i]]>cnt||c[L][R][b[i]]==cnt&&b[i]<num) cnt=c[L][R][b[i]],num=b[i];
}

int solve(int x,int y)
{
	int i,l,r;
	if(x>y) swap(x,y);
	for(i=1;i<=t;i++) if(x<=ed[i]) {l=i; break;}
	for(i=t;i;i--) if(y>=st[i]) {r=i; break;}
	if(l+1<=r-1) L=l+1,R=r-1; else L=R=0;
	cnt=f[L][R],num=d[L][R];
	if(l==r)
	{
		for(i=x;i<=y;i++) update(i);
		for(i=x;i<=y;i++) c[L][R][b[i]]--;
	}
	else{
		for(i=x;i<=ed[l];i++) update(i);
		for(i=st[r];i<=y;i++) update(i);
		for(i=x;i<=ed[l];i++) c[L][R][b[i]]--;
		for(i=st[r];i<=y;i++) c[L][R][b[i]]--;
	}
	return fb[num];
}

int main()
{
	cin>>n>>m;
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	prework();
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		ans=solve((x+ans-1)%n+1,(y+ans-1)%n+1);
		printf("%d\n",ans);
	}
	return 0;
}
已复制