Description
题目链接:P4168
给定一个长度为 $n$ 的序列,$m$ 次询问,每次询问输出区间众数,如果出现次数相同,输出编号小的。
强制在线。
$1\leq n\leq 4\times 10^4,1\leq m \leq 5\times 10^4,1\leq a_i\leq 10^9$
Solution
看到区间众数,自然而然就想到可以直接分块,时间复杂度 $O((N+M)\sqrt{N})$,空间复杂度 $O(N\sqrt{N})$,足矣通过此题,由于其他题解都写得很详细,这里就不再赘述。
那有没有更加优秀的算法呢?当然有,可以仿照P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的思路,预处理出 $[i,j]$ 块的众数出现次数,用 vector 按顺序存储每个数的所有元素出现位置,记录对应下标,每次询问的时候整块直接用预处理中的即可,散块个数最多为 $2\sqrt{N}$ 个,所以最多使答案增加 $2\sqrt{N}$,所以我们只需要扫一遍,判断这些数的出现个数是否能使答案加一即可。
总时间复杂度 $O((N+M)\sqrt{N})$,空间复杂度 $O(N)$,然而这种做法常数更小,所以跑得飞快,顺手卡一卡就拿到了最优解。
Code
普通分块:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#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%10+'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; } |
第二种做法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#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%10+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; } |