分块

分块 P2801 教主的魔法 分块即可，复制一个数组保持块内有序，然后用一个数组记录块整体的加减情况，就可以了。 代码： #include using namespace std; #define int long long const int N=1e6+5; int n,x,m,q; int a[N],b[N]; struct node{ int st,ed,tag; }k[N]; void change(int l,int r,int w){ int lx=(l-1)/x+1,rx=(r-1)/x+1; if(lx==rx){ for(int i=l;i=c) res++; return res; } for(int i=l;i=c) res++; for(int i=k[rx].st;i=c) res++; for(int i=lx+1;i=k[i].st&&id>n>>q; for(int i=1;i>a[i],b[i]=a[i]; x=sqrt(1.0*n); m=ceil(1.0*n/(1.0*x)); for(int i=1;i>op>>l>>r>>w; if(op=='M') change(l,r,w); else cout `#include using namespace std; #define int long long const int N=1e6+5; int n,x,m,q; int a[N],b[N]; struct node{ int st,ed,tag; }k[N]; void change(int l,int r,int w){ int lx=(l-1)/x+1,rx=(r-1)/x+1; if(lx==rx){ for(int i=l;ia[i]+=w; for(int i=k[lx].st;ik[lx].ed;i++) b[i]=a[i]; sort(b+k[lx].st,b+k[lx].ed+1); return; } for(int i=l;ik[lx].ed;i++) a[i]+=w; for(int i=k[lx].st;ik[lx].ed;i++) b[i]=a[i]; sort(b+k[lx].st,b+k[lx].ed+1); for(int i=k[rx].st;ia[i]+=w; for(int i=k[rx].st;ik[rx].ed;i++) b[i]=a[i]; sort(b+k[rx].st,b+k[rx].ed+1); for(int i=lx+1;ik[i].tag+=w; } int query(int l,int r,int c){ int res=0; int lx=(l-1)/x+1,rx=(r-1)/x+1; if(lx==rx){ for(int i=l;iif(a[i]+k[lx].tag>=c) res++; return res; } for(int i=l;ik[lx].ed;i++) if(a[i]+k[lx].tag>=c) res++; for(int i=k[rx].st;iif(a[i]+k[rx].tag>=c) res++; for(int i=lx+1;i int id=lower_bound(b+k[i].st,b+k[i].ed+1,c-k[i].tag)-b; if(id>=k[i].st&&idk[i].ed) res+=k[i].ed-id+1; } return res; } signed main(){ cin>>n>>q; for(int i=1;i>a[i],b[i]=a[i]; x=sqrt(1.0*n); m=ceil(1.0*n/(1.0*x)); for(int i=1;i k[i].st=(i-1)*x+1,k[i].ed=min(i*x,n); sort(b+k[i].st,b+k[i].ed+1); } while(q--){ char op; int l,r,w; cin>>op>>l>>r>>w; if(op=='M') change(l,r,w); else coutquery(l,r,w)"\n"; } return 0; }` P4168 [Violet] 蒲公英 预处理一下每两个块之间的众数以及前几个块每个值的个数， 先算出中间块的众数加上两边相等的数量，在看两边散块的值加上中间的值是否比当前答案大，都可以用预处理来的数据计算。 代码： #include using namespace std; #define int long long const int N=3e5+5; const int M=sqrt(N)+3; int n,x,m,q,ans; int a[N],b[N]; int cnt[N],f[M][N],g[M][M]; struct node{int st,ed;} k[N]; void init(){ for(int i=1;isum||(cnt[a[j]]==sum&&a[j]cnt[res]||(cnt[a[i]]==cnt[res]&&a[i]sum||(tot==sum&&a[i]sum||(tot==sum&&a[i]>n; for(int i=1;i>b[i],a[i]=b[i]; sort(b+1,b+1+n); for(int i=1;i>l>>r; ans=b[query(l,r)]; cout `#include using namespace std; #define int long long const int N=3e5+5; const int M=sqrt(N)+3; int n,x,m,q,ans; int a[N],b[N]; int cnt[N],f[M][N],g[M][M]; struct node{int st,ed;} k[N]; void init(){ for(int i=1;i for(int j=1;jf[i][j]=f[i-1][j]; for(int j=k[i].st;jk[i].ed;j++) f[i][a[j]]++; } for(int i=1;i memset(cnt,0,sizeof cnt); int res=0,sum=0; for(int i2=i;i2 for(int j=k[i2].st;jk[i2].ed;j++){ cnt[a[j]]++; if(cnt[a[j]]>sum||(cnt[a[j]]==sum&&a[j]a[j],sum=cnt[a[j]]; } g[i][i2]=res; } } memset(cnt,0,sizeof cnt); } int query(int l,int r){ int lx=(l-1)/x+1,rx=(r-1)/x+1; if(rx-lx1){ int res=0; for(int i=l;icnt[a[i]]=0; for(int i=l;i cnt[a[i]]++; if(cnt[a[i]]>cnt[res]||(cnt[a[i]]==cnt[res]&&a[i]a[i]; } return res; } int res=g[lx+1][rx-1]; int sum=f[rx-1][res]-f[lx][res]; for(int i=l;ik[lx].ed;i++) sum+=(a[i]==res),cnt[a[i]]=0; for(int i=k[rx].st;ia[i]==res),cnt[a[i]]=0; for(int i=l;ik[lx].ed;i++) cnt[a[i]]++; for(int i=k[rx].st;icnt[a[i]]++; for(int i=l;ik[lx].ed;i++){ int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]]; if(tot>sum||(tot==sum&&a[i]a[i]; } for(int i=k[rx].st;i int tot=f[rx-1][a[i]]-f[lx][a[i]]+cnt[a[i]]; if(tot>sum||(tot==sum&&a[i]a[i]; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i>b[i],a[i]=b[i]; sort(b+1,b+1+n); for(int i=1;ia[i]=lower_bound(b+1,b+1+n,a[i])-b; x=sqrt(1.0*n); m=(n+x-1)/x; for(int i=1;ik[i].st=(i-1)*x+1,k[i].ed=min(i*x,n); init(); for(int i=1;i int l,r; cin>>l>>r; ans=b[query(l,r)]; cout"\n"; } return 0; }` P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III 用一个数组表示每两个块之间众数的个数，一个 vector 表示每个值在原数组的下标，一个数组表示当前数在 vector 的下标。 答案先暂定为中间块的众数，然后再扫两边的散块，vector 往前或往后一个一个扫下标，直到超出左右两边的边界。 代码： #include using namespace std; #define int long long const int N=5e5+5,M=720; int n,x,m,q,ans; int a[N],b[N]; int in[N],st[M],ed[M]; int f[M][M],pos[N],cnt[N]; vector p[N]; void init(){ x=sqrt(1.0*n),m=(n+x-1)/x; sort(b+1,b+1+n); for(int i=1;ir||l>n) return 0; l=max(1ll,l),r=min(n,r); int ans=-1; if(in[l]==in[r]){ for(int i=l;i=st[in[r]];i--) while(pos[i]-ans>=0&&p[a[i]][pos[i]-ans]>=l) ans++; return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>q; for(int i=1;i>b[i],a[i]=b[i]; init(); while(q--){ int l,r; cin>>l>>r; l^=ans,r^=ans; ans=query(l,r); cout `#include using namespace std; #define int long long const int N=5e5+5,M=720; int n,x,m,q,ans; int a[N],b[N]; int in[N],st[M],ed[M]; int f[M][M],pos[N],cnt[N]; vectorint> p[N]; void init(){ x=sqrt(1.0*n),m=(n+x-1)/x; sort(b+1,b+1+n); for(int i=1;i in[i]=(i-1)/x+1; a[i]=lower_bound(b+1,b+1+n,a[i])-b; p[a[i]].push_back(i); pos[i]=p[a[i]].size()-1; } for(int i=1;ist[i]=(i-1)*x+1,ed[i]=min(i*x,n); for(int i=1;i memset(cnt,0,sizeof cnt); for(int j=i;j f[i][j]=f[i][j-1]; for(int k=st[j];ked[j];k++) f[i][j]=max(f[i][j],++cnt[a[k]]); } } } int query(int l,int r){ if(l>r||l>n) return 0; l=max(1ll,l),r=min(n,r); int ans=-1; if(in[l]==in[r]){ for(int i=l;icnt[a[i]]=0; for(int i=l;imax(ans,++cnt[a[i]]); return ans; } ans=f[in[l]+1][in[r]-1]; for(int i=l;ied[in[l]];i++) while(pos[i]+ansp[a[i]].size()&&p[a[i]][pos[i]+ans] for(int i=r;i>=st[in[r]];i--) while(pos[i]-ans>=0&&p[a[i]][pos[i]-ans]>=l) ans++; return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>q; for(int i=1;i>b[i],a[i]=b[i]; init(); while(q--){ int l,r; cin>>l>>r; l^=ans,r^=ans; ans=query(l,r); cout"\n"; } return 0; }` P4135 作诗 预处理前几个块每个值出现的次数、以及每两个块之间出现偶数次数的个数， 对于每次询问，枚举两边的散块，看是否会对中间块出现次数产生影响，对答案进行相应的加减即可。 代码： #include using namespace std; #define int long long const int N=1e5+5,M=720; int n,x,c,m,q,ans; int a[N],b[N]; int cnt[N],tag[N],f[M][N],g[M][M]; struct node{int st,ed;} k[N]; void init(){ for(int i=1;i1) g[i][i2]--; } } } } int query(int l,int r){ int lx=(l-1)/x+1,rx=(r-1)/x+1; if(rx-lx1) res--; } return res; } int res=g[lx+1][rx-1]; vector vc; for(int i=l;i0) res--; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>c>>q; for(int i=1;i>b[i],a[i]=b[i]; sort(b+1,b+1+n); for(int i=1;i>l>>r; l=(l+ans)%n+1,r=(r+ans)%n+1; if(l>r) swap(l,r); ans=query(l,r); cout `#include using namespace std; #define int long long const int N=1e5+5,M=720; int n,x,c,m,q,ans; int a[N],b[N]; int cnt[N],tag[N],f[M][N],g[M][M]; struct node{int st,ed;} k[N]; void init(){ for(int i=1;i for(int j=1;jf[i][j]=f[i-1][j]; for(int j=k[i].st;jk[i].ed;j++) f[i][a[j]]++; } for(int i=1;i memset(cnt,0,sizeof cnt); for(int i2=i;i2 g[i][i2]=g[i][i2-1]; for(int j=k[i2].st;jk[i2].ed;j++){ cnt[a[j]]++; if(cnt[a[j]]%2==0) g[i][i2]++; else if(cnt[a[j]]>1) g[i][i2]--; } } } } int query(int l,int r){ int lx=(l-1)/x+1,rx=(r-1)/x+1; if(rx-lx1){ int res=0; for(int i=l;icnt[a[i]]=0; for(int i=l;i cnt[a[i]]++; if(cnt[a[i]]%2==0) res++; else if(cnt[a[i]]>1) res--; } return res; } int res=g[lx+1][rx-1]; vectorint> vc; for(int i=l;ik[lx].ed;i++) tag[a[i]]=cnt[a[i]]=0; for(int i=k[rx].st;itag[a[i]]=cnt[a[i]]=0; for(int i=l;ik[lx].ed;i++) cnt[a[i]]++,vc.push_back(a[i]); for(int i=k[rx].st;icnt[a[i]]++,vc.push_back(a[i]); for(int i=0;ivc.size();i++){ int v=vc[i]; if(tag[v]) continue; tag[v]=1; if(cnt[v]%2==1&&(f[rx-1][v]-f[lx][v])%2==1) res++; if((cnt[v]%2)==0&&(f[rx-1][v]-f[lx][v])==0) res++; if(cnt[v]%2==1&&(f[rx-1][v]-f[lx][v])%2==0&&f[rx-1][v]-f[lx][v]>0) res--; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>c>>q; for(int i=1;i>b[i],a[i]=b[i]; sort(b+1,b+1+n); for(int i=1;ia[i]=lower_bound(b+1,b+1+n,a[i])-b; x=sqrt(1.0*n); m=(n+x-1)/x; for(int i=1;ik[i].st=(i-1)*x+1,k[i].ed=min(i*x,n); init(); while(q--){ int l,r; cin>>l>>r; l=(l+ans)%n+1,r=(r+ans)%n+1; if(l>r) swap(l,r); ans=query(l,r); cout"\n"; } return 0; }` P5356 [Ynoi Easy Round 2017] 由乃打扑克 区间加的操作不必多说， 对于查询区间…