2024/4/4 分块补题
P3203 [HNOI2010] 弹飞绵羊
分块跳跳跳，核心是每次跳出当前块，用 \(to[i]\) 表示跳到的位置。
#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
const int maxn = 2e5 + 10;
int be[maxn],L[maxn],R[maxn],cnt,B;
int n,m,a[maxn];
int to[maxn],f[maxn];
inline int query(int x){
int res=0;
while(x<=n){
res+=f[x];x=to[x];
}
return res;
}
int main(){
n=read();B=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
be[i]=(i-1)/B+1;
if(!L[be[i]])L[be[i]]=i,cnt++;
R[be[i]]=i;
}
for(int i=n;i>=1;i--){
if(i+a[i]>R[be[i]]){
to[i]=i+a[i];
f[i]=1;
}
else to[i]=to[i+a[i]],f[i]=f[i+a[i]]+1;
}
m=read();
while(m--){
int op=read(),pos=read()+1;
if(op==1)printf("%d\n",query(pos));
else {
int x=read();a[pos]=x;
for(int i=pos;i>=L[be[pos]];i--){
if(i+a[i]>R[be[i]]){
to[i]=i+a[i];
f[i]=1;
}
else to[i]=to[i+a[i]],f[i]=f[i+a[i]]+1;
}
}
}
return 0;
}
P4168 [Violet] 蒲公英
\(m\) 次询问，每次询问区间 \([L,R]\) 的众数，强制在线。
处理出整块 \(f_{i,j}\) 的众数是谁。
对于边角块出现的数，强行计数，用前缀和来处理整块的该数出现的次数。
#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
const int maxn = 40000 + 10;
const int maxm = 200 + 10;
int be[maxn],L[maxn],R[maxn],B,tot,cnt[maxn];
int n,m,a[maxn],tmp[maxn],mp[maxn];
int mx[maxm][maxm],f[maxm][maxn];
inline int query(int l,int r){
if(be[l]==be[r]){
for(int i=l;i<=r;i++)cnt[a[i]]=0;
for(int i=l;i<=r;i++)cnt[a[i]]++;
int maxx=0,res=0;
for(int i=l;i<=r;i++){
if(maxx<cnt[a[i]])maxx=cnt[a[i]],res=a[i];
else if(maxx==cnt[a[i]])res=min(res,a[i]);
}
return mp[res];
}
int res1=mx[be[l]+1][be[r]-1],maxx1=f[be[r]-1][res1]-f[be[l]][res1];
int res2=0,maxx2=0;
for(int i=l;i<=R[be[l]];i++)cnt[a[i]]=0;
for(int i=L[be[r]];i<=r;i++)cnt[a[i]]=0;
for(int i=l;i<=R[be[l]];i++){
cnt[a[i]]++;
if(a[i]==res1)maxx1++;
int temp=cnt[a[i]]+f[be[r]-1][a[i]]-f[be[l]][a[i]];
if(maxx2<temp)maxx2=temp,res2=a[i];
else if(maxx2==temp)res2=min(res2,a[i]);
}
for(int i=L[be[r]];i<=r;i++){
cnt[a[i]]++;
if(a[i]==res1)maxx1++;
int temp=cnt[a[i]]+f[be[r]-1][a[i]]-f[be[l]][a[i]];
if(maxx2<temp)maxx2=temp,res2=a[i];
else if(maxx2==temp)res2=min(res2,a[i]);
}
//cerr<<maxx1<<" "<<maxx2<<endl;//
//cerr<<res1<<" "<<res2<<endl;//
if(maxx1>maxx2)return mp[res1];
else if(maxx1==maxx2)return min(mp[res1],mp[res2]);
else return mp[res2];
}
int main(){
n=read();m=read();B=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read(),tmp[i]=a[i];
sort(tmp+1,tmp+1+n);
tot=unique(tmp+1,tmp+1+n)-(tmp+1);
for(int i=1;i<=n;i++){
be[i]=(i-1)/B+1;
if(!L[be[i]])L[be[i]]=i;
R[be[i]]=i;
int x=lower_bound(tmp+1,tmp+1+tot,a[i])-tmp;
mp[x]=a[i];a[i]=x;
}
for(int i=1;i<=be[n];i++){
for(int j=L[i];j<=R[i];j++)f[i][a[j]]++;
for(int j=1;j<=tot;j++)f[i][j]+=f[i-1][j];
}
for(int i=1;i<=be[n];i++){
memset(cnt,0,sizeof cnt);
int maxx=0,res=0;
for(int j=i;j<=be[n];j++){
for(int k=L[j];k<=R[j];k++){
cnt[a[k]]++;
if(cnt[a[k]]>maxx)maxx=cnt[a[k]],res=a[k];
else if(cnt[a[k]]==maxx)res=min(res,a[k]);
}
mx[i][j]=res;
}
}
int x=0;
while(m--){
int l0=read(),r0=read();
int l=(l0+x-1)%n+1,r=(r0+x-1)%n+1;
if(l>r)swap(l,r);
x=query(l,r);
printf("%d\n",x);
}
return 0;
}