基于分块思想，常用的有数列分块，之间分块，以及值域分块
把一个数组分为几个块，块内信息整体保存，两边散块进行暴力
首先进行分块
int len=sqrt(n);/*选择块长，也可以手动调节*/
for(int i=1;i<=n;i++)bl[i]=(i-1)/len+1;/*每个点所属块的编号*/
for(int i=1;i<=bl[n];i++){
st[i]=ed[i-1]+1;/*每个块的起始点*/
ed[i]=st[i]+len-1;/*每个块的终止点*/
}
ed[bl[n]]=n;/*最后长度不够len的块的终止点是n*/
同时可以用一些数组来初始化整个块内的信息，如果只有询问的话还可以有连续块的前缀和
for(int i=1;i<=n;i++)sum[bl[i]]+=a[i];
对于区间修改而言，若两个端点在一个块内，直接暴力修改，否则暴力修改两边散块，维护中间整块的信息及懒惰标记，若果修改是独立的，即可以单独为散块修改而不需要其他散块和整块的信息，那么可以稍微递归
inline void update(int l,int r,int x){
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)a[i]+=x,sum[bl[i]]+=x;/*暴力修改并维护块内的权值和*/
return;
}
update(l,ed[bl[l]],x),update(st[bl[r]],r,x);/*更新左右散块*/
for(int i=bl[l]+1;i<bl[r];i++)la[i]+=x/*整个块内的懒惰标记*/,sum[i]+=(ed[i]-st[i]+1)*x;/*维护整个块内的权值和*/
}
对于区间查询而言，若两端点在一个块内，直接暴力查询，否则查询两边散块，中间成块，若所查询的信息具有独立性，那么可以稍微递归
inline int ask(int l,int r){
int re=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)re+=a[i]+la[bl[i]];/*注意标记下方*/
return re;
}
re+=ask(l,ed[bl[l]])+ask(st[bl[r]],r);/*左右散块查询*/
for(int i=bl[l]+1;i<bl[r];i++)re+=sum[i];
return re;
}
查询区间和和区间开方。a[i]=1时开方无意义，每个数最多开方6次，维护区间和和一个标记，标记区间内是否每个元素都为1，全为1的块跳过即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],sum[N],la[N],bl[N],st[N],ed[N],len;
inline char gc(){static char buf[1<<22],*s=buf,*t=buf;return s==t&&(t=(s=buf)+fread(buf,1,1<<22,stdin),s==t)?EOF:*s++;}template<class T>inline T read(T&x){char c=gc(),f=x=0;while(c<'0'||c>'9')c=gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc();return x=f?-x:x;}inline void read(string&s){char c=gc();s="";while(c=='\n'||c==' ')c=gc();while(c!='\n'&&c!=' ')s+=c,c=gc();}template<class T,class...Args>inline void read(T&x,Args&...args){read(x),read(args...);}char buf[1<<22],*s=buf;inline void pc(char c){if(s-buf==1<<22)fwrite(buf,1,1<<22,stdout),s=buf;*s++=c;}template<class T>inline void put(T x){if(x<0)pc('-'),x=-x;if(x>9)put(x/10);pc(x%10|48);}
inline void update(int l,int r){
if(bl[l]==bl[r]){
if(la[bl[l]])return;/*整个区间都是1，无需开方直接跳过*/
for(int i=l;i<=r;i++)sum[bl[i]]-=a[i]/*维护区间和*/,a[i]=sqrt(a[i])/*进行开方*/,sum[bl[i]]+=a[i];/*修复区间和*/
if(sum[bl[l]]==ed[bl[l]]-st[bl[l]]+1/*由于不可能有<=0的数，所以区间和等于区间长度时及全等于1*/)la[bl[l]]=1;
return;
}
update(l,ed[bl[l]]);
update(st[bl[r]],r);
for(int i=bl[l]+1;i<bl[r];i++)update(st[i],ed[i]);
}
inline int ask(int l,int r){
int re=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)re+=a[i];
return re;
}
re+=ask(l,ed[bl[l]])+ask(st[bl[r]],r);
for(int i=bl[l]+1;i<bl[r];i++)re+=sum[i];
return re;
}
signed main() {
read(n);
len=400;
for(int i=1;i<=n;i++)bl[i]=(i-1)/len+1,read(a[i]),sum[bl[i]]+=a[i];
for(int i=1;i<=bl[n];i++){
st[i]=ed[i-1]+1;
ed[i]=st[i]+len-1;
if(ed[i]>n)ed[i]=n;
}
read(m);
while(m--){
int op,l,r;
read(op,l,r);
if(l>r)swap(l,r);
if(op)put(ask(l,r)),pc('\n');
else update(l,r);
}
fwrite(buf,1,s-buf,stdout);
return 0;
}
区间平方和区间开方，输出区间和。将区间开方视为区间加，维护每个数被平方的次数，若>1则打区间减的标记，若区间最大值=1则跳过开方操作，最后欧拉定力预处理2的k次方幂统计答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int n,m,len,a[N],bl[N],st[N],ed[N],la[N],cnt[N],mi[N],sum[N],p2[N],ans;
inline int po(int x,int k,int mod,int re=1){
for(;k;k>>=1,x=x*x%mod)(k&1)&&(re=re*x%mod);
return re;
}
inline void up(int x){
mi[x]=2e9;
for(int i=st[x];i<=ed[x];i++)mi[x]=min(mi[x],cnt[i]+la[x]);/*维护块内平方次数的最小值*/
}
inline void down(int x){
for(int i=st[x];i<=ed[x];i++)cnt[i]+=la[x];/*标记下放*/
la[x]=0;
}
inline void update(int l,int r){
if(bl[l]==bl[r]){
down(bl[l]);
for(int i=l;i<=r;i++){
if(a[i]==1)continue;
if(cnt[i])cnt[i]--;/*平方次数-1，相当于开方一次*/
else{
a[i]=sqrt(a[i]);
sum[bl[i]]+=a[i]==1;/*统计块内=1的数的个数*/
}
}
up(bl[l]);
return;
}
update(l,ed[bl[l]]);
update(st[bl[r]],r);
for(int i=bl[l]+1;i<bl[r];i++){
if(sum[i]==ed[i]-st[i]+1)continue;/*无需再开方*/
if(mi[i])mi[i]--,la[i]--;/*直接修改整块平方的标记*/
else update(st[i],ed[i]);
}
}
inline void add(int l,int r){
if(bl[l]==bl[r]){
down(bl[l]);
for(int i=l;i<=r;i++)cnt[i]++;/*平方次数+1*/
up(bl[l]);
return;
}
add(l,ed[bl[l]]);
add(st[bl[r]],r);
for(int i=bl[l]+1;i<bl[r];i++)mi[i]++,la[i]++;
}
signed main(){
scanf("%lld%lld",&n,&m);
len=sqrt(n);
for(int i=1;i<=n;i++)bl[i]=(i-1)/len+1,scanf("%lld",a+i);
for(int i=1;i<=bl[n];i++){
st[i]=ed[i-1]+1;
ed[i]=st[i]+len-1;
}
ed[bl[n]]=n;
p2[0]=1;
for(int i=1;i<=m;i++)p2[i]=(p2[i-1]<<1)%(mod-1);
while(m--){
int op,l,r;
scanf("%lld%lld%lld",&op,&l,&r);
if(op==1)update(l,r);
else add(l,r);
}
for(int i=1;i<=bl[n];i++)down(i);
for(int i=1;i<=n;i++){
if(a[i]==1)ans++;
else ans+=po(a[i],p2[cnt[i]],mod);
ans%=mod;
}
printf("%lld",ans%mod);
return 0;
}
区间加和查询a[x]在过去多少秒时间内不小于y，初始0秒，第i个操作在第i秒。在时间轴上分块，对每个数单独处理，将询问离线并排序，对于t时刻给[l,r]+x，分成两部分，在处理第l个数时将时刻[t,m]+x，在处理第r+1个数时将时刻[t,m]-x来抵消影响
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],ans[N],c[N],la[N],bl[N],st[N],ed[N],tot,len;
vector<int>o[N];
struct query{int op,t,x,v;bool operator<(const query&a)const{return x==a.x?t<a.t:x<a.x;}}q[N<<1];
inline void update(int l,int r,int x){
if(bl[l]==bl[r]){
o[bl[l]].clear();
for(int i=l;i<=r;i++)c[i]+=x;/*暴力修改*/
for(int i=st[bl[l]];i<=ed[bl[l]];i++)o[bl[i]].push_back(c[i]);/*维护块内信息*/
sort(o[bl[l]].begin(),o[bl[l]].end());/*调整*/
return;
}
update(l,ed[bl[l]],x);update(st[bl[r]],r,x);
for(int i=bl[l]+1;i<bl[r];i++)la[i]+=x;/*懒惰标记*/
}
inline int ask(int l,int r,int x){
int re=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)re+=(c[i]+la[bl[i]]>=x);/*注意懒惰标记不下放*/
return re;
}
re+=ask(l,ed[bl[l]],x)+ask(st[bl[r]],r,x);
for(int i=bl[l]+1;i<bl[r];i++)re+=o[i].size()-(lower_bound(o[i].begin(),o[i].end(),x-la[i])-o[i].begin());/*没个整块内>=x的数的个数*/
return re;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int op;ans[i]=-1;
cin>>op;
if(op==1){
int l,r,x;
cin>>l>>r>>x;
q[++tot]={1,i,l,x};
q[++tot]={1,i,r+1,-x};
}
else{
int x,y;
cin>>x>>y;
q[++tot]={2,i,x,y};
}
}
sort(q+1,q+1+tot);
len=sqrt(++m);
for(int i=1;i<=m;i++)bl[i]=(i-1)/len+1,o[bl[i]].push_back(0);
for(int i=1;i<=bl[m];i++){
st[i]=ed[i-1]+1;
ed[i]=st[i]+len-1;
}
ed[bl[m]]=m;
for(int i=1;i<=tot;i++){
if(q[i-1].x!=q[i].x)update(1,m,a[q[i].x]-a[q[i-1].x]);/*新处理一个数，所有时刻全部更新*/
if(q[i].op==1)update(q[i].t+1,m,q[i].v);/*在这和之后的时刻中进行更新*/
else ans[q[i].t]=ask(1,q[i].t,q[i].v);/*查询初始到不包括这一秒*/
}
for(int i=1;i<m;i++)if(ans[i]!=-1)cout<<ans[i]<<'\n';
return 0;
}
给定汉子种类c，每次询问[l,r]内有多少个数出现次数为正偶数次。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int bl[N],st[N],ed[N],len,a[N],la,n,m,c,cnt[1010][N],ans[1010][1010],t[N];
inline int ask(int l,int r){
int re=0;
if(bl[l]+1>=bl[r]){/*处于相邻的块也是可以直接算的*/
for(int i=l;i<=r;i++){
t[a[i]]++;
if(!(t[a[i]]&1))re++;
else if(t[a[i]]>2)re--;
}
for(int i=l;i<=r;i++)t[a[i]]--;
return re;
}
re=ans[bl[l]+1][bl[r]-1];/*暂时的答案*/
for(int i=l;i<=ed[bl[l]];i++){
t[a[i]]++;/*左边散块的桶*/
int tmp=cnt[bl[r]-1][a[i]]-cnt[bl[l]][a[i]];/*前缀和查分求出当前颜色在整块中出现的次数*/
if(!((t[a[i]]+tmp)&1))re++;/*随时维护*/
else if(t[a[i]]+tmp>2)re--;
}
for(int i=st[bl[r]];i<=r;i++){
t[a[i]]++;/*右边散块的桶*/
int tmp=cnt[bl[r]-1][a[i]]-cnt[bl[l]][a[i]];
if(!((t[a[i]]+tmp)&1))re++;
else if(t[a[i]]+tmp>2)re--;
}
for(int i=l;i<=ed[bl[l]];i++)t[a[i]]--;/*桶复原*/
for(int i=st[bl[r]];i<=r;i++)t[a[i]]--;
return re;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>c>>m;
len=sqrt(n);
for(int i=1;i<=n;i++)bl[i]=(i-1)/len+1;
for(int i=1;i<=bl[n];i++){
st[i]=ed[i-1]+1;
ed[i]=st[i]+len-1;
}
ed[bl[n]]=n;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[bl[i]][a[i]]++;/*块bl[i]内颜色a[i]出现的次数*/
}
for(int i=1;i<=bl[n];i++)for(int j=0;j<=c;j++)cnt[i][j]+=cnt[i-1][j];/*处理成颜色j出现次数的前缀和*/
for(int i=1;i<=bl[n];i++){
for(int j=i;j<=bl[n];j++){
ans[i][j]=ans[i][j-1];/*处理块i到块j中出现次数为正偶数次的数的个数*/
for(int k=st[j];k<=ed[j];k++){
t[a[k]]++;/*当前颜色的桶*/
if(!(t[a[k]]&1))ans[i][j]++;/*随时维护*/
else if(t[a[k]]>2)ans[i][j]--;/*变成奇数就-1*/
}
}
memset(t,0,sizeof(t));
}
while(m--){
int l,r;
cin>>l>>r;
l=(l+la)%n+1,r=(r+la)%n+1;
if(l>r)swap(l,r);
cout<<(la=ask(l,r))<<'\n';
}
return 0;
}
支持两种操作，区间循环右移一位，查询区间内x的出现次数。用deque维护，再开个桶统计每个块中各颜色的出现次数。
inline void modify(int l,int r){
if(bl[l]==bl[r]){
int x=q[bl[l]][r-st[bl[l]]];
q[bl[l]].erase(q[bl[l]].begin()+(r-st[bl[l]]));
q[bl[l]].insert(q[bl[l]].begin()+(l-st[bl[l]]),x);
return;
}
int x=q[bl[r]][r-st[bl[r]]];
q[bl[l]].insert(q[bl[l]].begin()+(l-st[bl[l]]),x);
cnt[bl[l]][x]++;
cnt[bl[r]][x]--;
q[bl[r]].erase(q[bl[r]].begin()+(r-st[bl[r]]));
for(int i=bl[l]+1;i<=bl[r];i++){
int x=q[i-1].back();
q[i].push_front(x);
cnt[i][x]++;
q[i-1].pop_back();
cnt[i-1][x]--;
}
}
inline int query(int l,int r,int k){
int re=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;i++)re+=q[bl[l]][i-st[bl[l]]]==k;
return re;
}
re+=query(l,ed[bl[l]],k)+query(st[bl[r]],r,k);
for(int i=bl[l]+1;i<bl[r];i++)re+=cnt[i][k];
return re;
}