LuoguP4168 [Violet]蒲公英

(Updated: )
oi

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;
}