LuoguP4168 [Violet]蒲公英
Description
题目链接：P4168
给定一个长度为 n 的序列，m 次询问，每次询问输出区间众数，如果出现次数相同，输出编号小的。
强制在线。
1leq nleq 4times 10^4,1leq m leq 5times 10^4,1leq a_ileq 10^9
Solution
看到区间众数，自然而然就想到可以直接分块，时间复杂度 O((N M)sqrt{N})，空间复杂度 O(Nsqrt{N})，足矣通过此题，由于其他题解都写得很详细，这里就不再赘述。
那有没有更加优秀的算法呢？当然有，可以仿照P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的思路，预处理出 [i,j] 块的众数出现次数，用 vector 按顺序存储每个数的所有元素出现位置，记录对应下标，每次询问的时候整块直接用预处理中的即可，散块个数最多为 2sqrt{N} 个，所以最多使答案增加 2sqrt{N}，所以我们只需要扫一遍，判断这些数的出现个数是否能使答案加一即可。
总时间复杂度 O((N M)sqrt{N})，空间复杂度 O(N)，然而这种做法常数更小，所以跑得飞快，顺手卡一卡就拿到了最优解。
Code
普通分块：
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=4e4 10,S=500,M=N/S 10;
int n,m,a[N],b[N],cnt,tot,Ans,L[M],R[M],Cnt[M][N],F[M][M],sum[N];
#define GetCnt(i,j,k) (Cnt[(j)][(k)]-Cnt[(i)-1][(k)])
I void Build(){
RI i,j,k,t,now;for(sort(b,b n),cnt=unique(b,b n)-b,i=0;i<n;i ) a[i]=lower_bound(b,b cnt,a[i])-b;
for(i=0;i<n;i ) if(i%S==0) R[tot]=i-1,L[ tot]=i;R[tot]=n-1;
for(i=1;i<=tot;i ) for(j=L[i];j<=R[i];j ) Cnt[i][a[j]] ;for(i=1;i<=tot;i ) for(j=0;j<cnt;j ) Cnt[i][j] =Cnt[i-1][j];
for(i=1;i<=tot;i ) for(now=a[j=i];j<=tot;j ) for(k=L[j];k==R[j] 1&&(F[i][j]=now),k<=R[j];k )
if(GetCnt(i,j,a[k])>GetCnt(i,j,now)GetCnt(i,j,a[k])==GetCnt(i,j,now)&&a[k]<now) now=a[k];
}
vector<int> v;
I int Query(CI Ll,CI Rr){
RI i,j,l,r,now;l=Ll/S 1,r=Rr/S 1;v.clear();memset(sum,0,sizeof(sum));
if(l==r){for(i=Ll;i<=Rr;i ) v.push_back(a[i]),now=a[i],sum[a[i]] ;for(auto i:v) if(sum[i]>sum[now]sum[i]==sum[now]&&i<now) now=i;return b[now];}
if(L[l]^Ll){for(i=Ll;i<=R[l];i ) v.push_back(a[i]),sum[a[i]] ;l ;}
if(R[r]^Rr){for(i=L[r];i<=Rr;i ) v.push_back(a[i]),sum[a[i]] ;r--;}
now=F[l][r];for(auto i:v) if(sum[i] GetCnt(l,r,i)>sum[now] GetCnt(l,r,now)sum[i] GetCnt(l,r,i)==sum[now] GetCnt(l,r,now)&&i<now) now=i;
return b[now];
}
int main(){
RI i,l,r,p=0;for(read(n,m),i=0;i<n;i ) read(a[i]),b[i]=a[i];
for(Build();m--;) read(l,r),l=(l p-1)%n,r=(r p-1)%n,l>r&&(swap(l,r),0),writeln(p=Query(l,r));return 0;
}第二种做法：
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear(){fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x){x=0;W(!isdigit(oc=tc()));W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x){W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=4e4 2,S=106,M=N/S 2;
int n,m,a[N],b[N],cnt,tot,Ans,Cnt[N],F[M][M],pos[N],DP[M][M],SZ[N];
vector<int> v[N];
I void Build(){
RI i,j,k,t,now;for(sort(b,b n),cnt=unique(b,b n)-b,i=0;i<n;i )
a[i]=lower_bound(b,b cnt,a[i])-b,pos[i]=SZ[a[i]] ,v[a[i]].push_back(i);tot=(n-1)/S 1;
for(i=1;i<=tot;i ) for(memset(Cnt,0,sizeof(Cnt)),now=a[j=i];j<=tot;j )
for(k=(j-1)*S;k==min(j*S-1,n-1) 1&&(F[i][j]=Cnt[now],DP[i][j]=now),k<=min(j*S-1,n-1);k ) if( Cnt[a[k]],Cnt[a[k]]>Cnt[now](Cnt[a[k]]==Cnt[now]&&a[k]<now)) now=a[k];
}
I int Query(CI Ll,CI Rr){
RI i,j,l=Ll/S 1,r=Rr/S 1,now=0,zz=0;if(l==r){
for(now=0,i=Ll;i<=Rr;i ){W(pos[i] now<SZ[a[i]]&&v[a[i]][pos[i] now]<=Rr) zz=a[i],now ;if(pos[i] now-1<SZ[a[i]]&&v[a[i]][pos[i] now-1]<=Rr&&zz>a[i]) zz=a[i];}
return b[zz];
}if(l 1<=r-1) now=F[l 1][r-1],zz=DP[l 1][r-1];
for(i=Ll;i<=min(l*S-1,n-1);i ){W(pos[i] now<SZ[a[i]]&&v[a[i]][pos[i] now]<=Rr) zz=a[i],now ;if(pos[i] now-1<SZ[a[i]]&&v[a[i]][pos[i] now-1]<=Rr&&zz>a[i]) zz=a[i];}
for(i=(r-1)*S;i<=Rr;i ){W(pos[i]-now>=0&&v[a[i]][pos[i]-now]>=Ll) zz=a[i],now ;if(pos[i]-(now-1)>=0&&v[a[i]][pos[i]-(now-1)]>=Ll&&zz>a[i]) zz=a[i];}
return b[zz];
}
int main(){
RI i,l,r,p=0;for(read(n,m),i=0;i<n;i ) read(a[i]),b[i]=a[i];
for(Build();m--;) read(l,r),l=l p-1,l>=n&&(l%=n,0),r=r p-1,r>=n&&(r%=n,0),l>r&&(swap(l,r),0),writeln(p=Query(l,r));
return clear(),0;
}
