這道題算是好好寫了。寫了三種方法。

有一個好像是$qwq$$N\sqrt(N)$的方法，，但是懇請大佬們幫我看看為什么這么慢$qwq$（后面的第三種）

注:$pos[i]$表示$i$屬于第$pos[i]$塊。

---

第一種是統計所有可能的塊組成的區間中（第i塊到第j塊）,每個數出現的次數，記做$f[i][j][k]$，和所有可能的塊組成的區間的答案，記做$h[i][j]$。

然后每次先把整塊的答案作為初始答案，然后對于散塊中的每個值$vl$，暴力修改對應的$f[i][j][vl]$,更新答案。

當塊長取$N^\frac{2}{3}$,時間復雜度$O(N^\frac{5}{3})$級。

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ull unsigned long long #define ll long long #define R register int #define pause (for(R i=1;i<=10000000000;++i)) #define OUT freopen("out.out","w",stdout); using namespace std; namespace Fread {static char B[1<<15],*S=B,*D=B;#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)inline int g() {R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;} inline bool isempty(const char& ch) {return ch<=36||ch>=127;}inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));} }using Fread::g; using Fread::gs; const int N=40010,M=37; int n,m,tot,T,lst; int f[M][M][N],h[M][M],vl[N],a[N],b[N],pos[N]; inline void PRE() { R mx=0,ans=0;for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1;for(R j=1,L=pos[n];j<=L;++j,mx=0,ans=0) for(R t=j;t<=L;++t) {memcpy(f[j][t],f[j][t-1],sizeof(f[j][t-1]));for(R i=(t-1)*T+1,LL=min(t*T,n);i<=LL;++i) ++f[j][t][a[i]];for(R i=tot;i;--i) if(f[j][t][i]>=mx) mx=f[j][t][i],ans=i;h[j][t]=ans;} } signed main() { #ifdef JACKfreopen("NOIPAK++.in","r",stdin);OUT; #endifn=g(),m=g(),T=n/pow(n,1.0/3);for(R i=1;i<=n;++i) a[i]=g(); memcpy(b,a,sizeof(a));sort(b+1,b+n+1); tot=unique(b+1,b+n+1)-b-1;for(R i=1;i<=n;++i) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;memcpy(vl,b,sizeof(int)*(tot+1)); PRE();for(R i=1,l,r;i<=m;++i) { R mx=0,ans=0;l=(g()+lst-1)%n+1,r=(g()+lst-1)%n+1; l>r?swap(l,r):(void)0;R p=pos[l]+1,q=pos[r]-1; ans=h[p][q],mx=f[p][q][ans];if(pos[l]==pos[r]) { for(R i=l;i<=r;++i) { ++f[p][q][a[i]];if(f[p][q][a[i]]>mx||(f[p][q][a[i]]==mx&&a[i]<ans)) mx=f[p][q][a[i]],ans=a[i];} for(R i=l;i<=r;++i) --f[p][q][a[i]];} else { ans=h[p][q],mx=f[p][q][ans];for(R i=l,L=pos[l]*T;i<=L;++i) { ++f[p][q][a[i]];if(f[p][q][a[i]]>mx||(f[p][q][a[i]]==mx&&a[i]<ans)) mx=f[p][q][a[i]],ans=a[i];} for(R i=(pos[r]-1)*T+1;i<=r;++i) { ++f[p][q][a[i]];if(f[p][q][a[i]]>mx||(f[p][q][a[i]]==mx&&a[i]<ans)) mx=f[p][q][a[i]],ans=a[i];} for(R i=l,L=pos[l]*T;i<=L;++i) --f[p][q][a[i]];for(R i=(pos[r]-1)*T+1;i<=r;++i) --f[p][q][a[i]];} printf("%d\n",lst=vl[ans]); } }

---

第二種是預處理出所有可能的塊組成的區間中（第$i$塊到第$j$塊）的答案$f[i][j]$,并且拿一個$vector$存每個數$vl$出現的位置$s[vl][1...n]$。

答案初始化為整塊的答案，然后對于散塊中的每個數$vl$,在$s[vl]$中二分出$[l,r]$的最小和最大的位置的下標，相減就是$[l,r]$有多少個$vl$,然后更新答案。

當塊長取$\sqrt{\frac{N}{logN}}$,時間復雜度$O(N\sqrt{NlogN})$。

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ull unsigned long long #define ll long long #define R register int #define pause (for(R i=1;i<=10000000000;++i)) #define OUT freopen("out.out","w",stdout); using namespace std; namespace Fread {static char B[1<<15],*S=B,*D=B;#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)inline int g() {R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;} inline bool isempty(const char& ch) {return ch<=36||ch>=127;}inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));} }using Fread::g; using Fread::gs; map<int,int> mp; const int N=40010; int n,m,T,tot,lst; vector<int> s[N]; #define pb push_back int f[10010][10010],cnt[N],p[N],pos[N],a[N],b[N],vl[N]; inline void PRE(int p) { R ans=0,mx=0; memset(cnt,0,sizeof(cnt)); for(R t=p,lim=pos[n];t<=lim;++t) {for(R i=(t-1)*T+1,lim=min(n,t*T);i<=lim;++i) {if(++cnt[a[i]]>mx||(cnt[a[i]]==mx&&a[i]<ans)) mx=cnt[a[i]],ans=a[i];} f[p][t]=ans;} } inline int calc(int l,int r,int x) {return upper_bound(s[x].begin(),s[x].end(),r)-lower_bound(s[x].begin(),s[x].end(),l);} inline int solve(int l,int r) { R mx=0,ret=0; if(pos[l]==pos[r]) { memset(cnt,0,sizeof(cnt)); for(R i=l;i<=r;++i) if(++cnt[a[i]]>mx||(cnt[a[i]]==mx&&a[i]<ret)) ret=a[i],mx=cnt[a[i]];} else { ret=f[pos[l]+1][pos[r]-1],mx=calc(l,r,ret);for(R i=l,lim=pos[l]*T;i<=lim;++i) { R t=calc(l,r,a[i]);if(t>mx||(t==mx&&a[i]<ret)) ret=a[i],mx=t;} for(R i=(pos[r]-1)*T+1;i<=r;++i) { R t=calc(l,r,a[i]);if(t>mx||(t==mx&&a[i]<ret)) ret=a[i],mx=t;}} return ret; } signed main() { #ifdef JACKfreopen("NOIPAK++.in","r",stdin);OUT; #endifn=g(),m=g();//,T=n/sqrt(n*log2(n));T=qpow(n,1.0/4);for(R i=1;i<=n;++i) a[i]=g();memcpy(b,a,sizeof(a)); sort(b+1,b+n+1);tot=unique(b+1,b+n+1)-b-1; memcpy(vl,b,sizeof(int)*(tot+1));for(R i=1;i<=n;++i) a[i]=lower_bound(b+1,b+tot+1,a[i])-b,s[a[i]].pb(i);for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1;for(R i=1;i<=pos[n];++i) PRE(i);for(R i=1,l,r;i<=m;++i) {l=(g()+lst-1)%n+1,r=(g()+lst-1)%n+1; l>r?swap(l,r):(void)0;printf("%d\n",lst=vl[solve(l,r)]);} }

---

第三種按理說是復雜度最優秀的，但是跑的不是很快$qwq$。

同第二種，預處理出所有可能的塊組成的區間中（第i塊到第j塊）的答案$f[i][j]$,并且拿一個$vector$存每個數$vl$出現的位置$s[vl][1...n]$。

然后預處理$a[i]$是整個數列中的第幾個$a[i]$,出第$1$到第$i$塊中最靠后的$vl$是第幾個$vl$，記為$d[i][vl]$，預處理出第$n$塊到第$i$塊中最靠前的$vl$是第幾個$vl$,記為$h[i][vl]$。

對于左邊散塊中的$vl$，查一下$d[pos[r]-1][vl]$,和右邊散塊中是否有更靠后的$vl$(可以事先用一個數組存起來)，然后可以求出這個區間有多少個$vl$(每一個$vl$是第幾個$vl$已經知道了),更新答案。

當塊長取$\sqrt{n}$時，時間復雜度為O(N\sqrt{N})級(不知道推沒推錯)。

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ull unsigned long long #define ll long long #define R register int #define pause (for(R i=1;i<=10000000000;++i)) #define OUT freopen("out.out","w",stdout); using namespace std; namespace Fread {static char B[1<<15],*S=B,*D=B;#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)inline int g() {R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;} inline bool isempty(const char& ch) {return ch<=36||ch>=127;}inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));} }using Fread::g; using Fread::gs; const int N=40010,M=1000; int n,m,T,tot,lst; vector<int> s[N]; #define pb push_back int f[M][M],cnt[N],P[N],pos[N],a[N],b[N],vl[N],h[M][N],d[M][N],c[M][M]; inline void PRE(int p) { R ans=0,mx=0; memset(cnt,0,sizeof(cnt)); for(R t=p,lim=pos[n];t<=lim;++t) {for(R i=(t-1)*T+1,lim=min(n,t*T);i<=lim;++i) {if(++cnt[a[i]]>mx||(cnt[a[i]]==mx&&a[i]<ans)) mx=cnt[a[i]],ans=a[i];} f[p][t]=ans,c[p][t]=mx;} } inline int solve(int l,int r) { R mx=0,ret=0,p=pos[l]+1,q=pos[r]-1; if(pos[l]==pos[r]) { memset(cnt,0,sizeof(cnt)); for(R i=l;i<=r;++i) if(++cnt[a[i]]>mx||(cnt[a[i]]==mx&&a[i]<ret)) ret=a[i],mx=cnt[a[i]];} else { ret=f[p][q],mx=c[p][q]; memset(cnt,0x3f,sizeof(cnt));for(R i=l,L=pos[l]*T;i<=L;++i) if(cnt[a[i]]==0x3f3f3f3f) cnt[a[i]]=P[i];for(R i=q*T+1;i<=r;++i) {R tmp=P[i]+1-min(cnt[a[i]],h[p][a[i]]);if(tmp>mx||(tmp==mx&&a[i]<ret)) ret=a[i],mx=tmp;cnt[a[i]]=P[i];} for(R i=l,L=pos[l]*T;i<=L;++i) {R tmp=max((cnt[a[i]]==0x3f3f3f3f?0:cnt[a[i]]),d[q][a[i]])-P[i]+1;if(tmp>mx||(tmp==mx&&a[i]<ret)) ret=a[i],mx=tmp;} } return ret; } signed main() { #ifdef JACKfreopen("NOIPAK++.in","r",stdin);OUT; #endifn=g(),m=g(); T=pow(n,1/2.3);//好像更小一點更快（也不是越小越快）for(R i=1;i<=n;++i) a[i]=g();memcpy(b,a,sizeof(a)); sort(b+1,b+n+1);tot=unique(b+1,b+n+1)-b-1; memcpy(vl,b,sizeof(int)*(tot+1));for(R i=1;i<=n;++i) a[i]=lower_bound(b+1,b+tot+1,a[i])-b,s[a[i]].pb(i);for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1; for(R i=1;i<=n;++i) P[i]=++cnt[a[i]]; memset(cnt,0,sizeof(cnt)); memset(h[pos[n]+1],0x3f,sizeof(h[pos[n]+1]));for(R t=pos[n];t;--t) { memcpy(h[t],h[t+1],sizeof(h[t+1]));for(R i=min(n,t*T);i>(t-1)*T;--i) h[t][a[i]]=P[i];} for(R t=1;t<=pos[n];++t) { memcpy(d[t],d[t-1],sizeof(d[t-1]));for(R i=(t-1)*T+1,L=t*T;i<=L;++i) d[t][a[i]]=P[i];} for(R i=1;i<=pos[n];++i) PRE(i); for(R i=1,l,r;i<=m;++i) {l=(g()+lst-1)%n+1,r=(g()+lst-1)%n+1; l>r?swap(l,r):(void)0;printf("%d\n",lst=vl[solve(l,r)]);} }

---

2019.06.28

?

轉載于:https://www.cnblogs.com/Jackpei/p/11105253.html

總結

以上是生活随笔為你收集整理的Luogu P4168 [Violet]蒲公英 分块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。