本文共 1759 字，大约阅读时间需要 5 分钟。
昨天对着代码看了一晚上
然后相当玄学
#include #include #include #include #include #include using namespace std;int belong[100100],f[1000][1000],sz,blocknum,n,val[100100],id=0,cnt[100100],a[100100];vector Vec[100100];map To;void calbe(int n){ for(int i=1;i<=n;i++) belong[i]=(i-1)/sz+1;}void pre(int x){ memset(cnt,0,sizeof(cnt)); int ans=0,ansto=0; for(int i=(x-1)*sz+1;i<=n;i++){ cnt[a[i]]++; if(cnt[a[i]]>ansto||(val[a[i]]<=val[ans]&&cnt[a[i]]>=ansto)) ans=a[i],ansto=cnt[a[i]]; f[x][belong[i]]=ans; }}int query(int l,int r,int c){ return upper_bound(Vec[c].begin(),Vec[c].end(),r)-lower_bound(Vec[c].begin(),Vec[c].end(),l);}int query(int l,int r){ int lsx=belong[l]; int rex=belong[r]; int ans=0,ansto=0,mid; for(int i=l;i<=min(lsx*sz,r);i++) if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto)) ans=a[i],ansto=mid; if(lsx!=rex){ for(int i=(rex-1)*sz+1;i<=r;i++) if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto)) ans=a[i],ansto=mid; if(lsx+1<=rex-1) if((mid=query(l,r,f[lsx+1][rex-1]))>ansto||(val[f[lsx+1][rex-1]]<=val[ans]&&mid>=ansto)) ans=f[lsx+1][rex-1],ansto=mid; } return ans;}int main(){ // freopen("1.in","r",stdin); // freopen("test.out","w",stdout); scanf("%d",&n); sz=150; blocknum=n/sz; if(n%sz) blocknum++; calbe(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(!To[a[i]]){ To[a[i]]=++id; val[id]=a[i]; } a[i]=To[a[i]]; Vec[a[i]].push_back(i); } for(int i=1;i<=blocknum;i++) pre(i); for(int i=1;i<=n;i++){ int l,r; scanf("%d %d",&l,&r); printf("%d\n",val[query(l,r)]); } return 0; }
转载于:https://www.cnblogs.com/dreagonm/p/10048516.html