本文共 3098 字，大约阅读时间需要 10 分钟。

update2018.1.3

今天晚上，陈队问我是怎么做的，我说分块

才想起有一个log没有去掉 于是想了一下，还真的可以去掉这个log 我们先对数集进行离散化 考虑从后往前扫，一次加入数字 然后加入一个数的时候，更新一下这个数出现的最后两个位置 那么出现了一次的就是这两个点之间 然后我们当遇到块的端点的时候，然后就从大到小扫一下数组，设这两个位置为$l,r$然后我们就对在$l,r$区间里面的块端点$j$,$f[i][j]$加入这个数。因为是从大到小扫的，因此可以保证值都是最大的，然后当一个块加入够数的时候，就不加了。 这个过程显然可以用一个并查集维护，维护下一个还可以加数的块在哪里 这样的话，复杂度就是$n\sqrt{n}$了，感觉还是很优秀哒

题解

网上有很多乱七八糟的方法

有KDtree，树套树等等一大堆。。 出题人的贴吧大家也可以看一看 然而我用的是分块。。设B为块的大小 我们就预处理f[i][j]表示第i块到第j块的一个表，储存2*B+1个只出现了一次的数。。 至于为什么是2*B+1，那是因为零散的地方最多就是2*B，也就是有2*B个出现一次的数可能会GG，这时候我们要保证要是有解的话一定要找出来。。 然后到时候就把整块的拿出来，然后用零散的更新一下他就可以了。。要注意的是他们也能作为答案，更新一下就好了。。 至于怎么求f[i][j]，我用了个傻逼的方法，多了个log。。然而居然过了。。可能比较难卡然后我正在想怎么优化的时候，他居然过了。。 还和FYC的可持久化树套树差不多速度，都是很慢。。 于是优化就没想了，留坑。。已填 时间复杂度$O(n\sqrt{n})$

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=100005;const int NN=320;int n,m,nn;int a[N];int cnt,L[NN],R[NN],belong[N]; int mymin (int x,int y){ return x
          
           y?x:y;}void prepare() { L[1]=1;belong[1]=1;cnt=1; for (int u=1;u<=n;u++) { belong[u]=cnt; if (u%nn==0) { R[cnt]=u; cnt++; L[cnt]=u+1; } } cnt=belong[n];R[cnt]=n;}int f[NN][NN][2*NN];//第i块到第j块的表int c[N];//这个数字出现了多少次set
           
             ooo;set
            
             ::iterator it;int next[N],last[N];int vis[N],shen;//这个数字有没有用过bool cmp (int x,int y){ return x>y;}inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void prepare1 ()//预处理f数组 和last和next数组{ memset(vis,127,sizeof(vis)); for (int u=n;u>=1;u--) { next[u]=vis[a[u]]; vis[a[u]]=u; } memset(vis,-1,sizeof(vis)); for (int u=1;u<=n;u++) { last[u]=vis[a[u]]; vis[a[u]]=u; } for (int u=1;u<=cnt;u++) { ooo.clear(); memset(c,0,sizeof(c)); for (int i=L[u];i<=n;i++) c[a[i]]++;//这个数又出现了一次 for (int i=n;i>=1;i--) if (c[i]==1)//这个数刚好出现了一次 ooo.insert(i); for (int i=n;i>=R[u];i--)//扫回去 { if (i==R[belong[i]])//如果已经到了一个块的右端点，那么到他下一个块的答案就可以统计了 { int o=belong[i]+1;//下一个块 /*printf("%d %d %d\n",u,i,c[9]); system("pause");*/ if (o<=cnt) { for (set
             
              ::reverse_iterator it=ooo.rbegin();it!=ooo.rend();it++) { f[u][o][0]++; f[u][o][f[u][o][0]]=(*it); if (f[u][o][0]>nn*2) break; } } } c[a[i]]--; if (c[a[i]]==1) ooo.insert(a[i]);//先把他弄进来，以后再踢掉他，所以这里的话会有2*sqrtn个数 if (c[a[i]]==0) ooo.erase(a[i]); } }}void Ins (){ n=read();m=read();nn=sqrt(n); for (int u=1;u<=n;u++) a[u]=read();} int solve1 (int l,int r)//这一个的答案 { int ans=0; if (belong[l]==belong[r])//如果在同一个块中暴力搞就好了 { for (int u=l;u<=r;u++) if (last[u]
              
               r) ans=mymax(ans,a[u]); return ans; } shen++; int x=belong[l],y=belong[r]; for (int u=l;u<=R[x];u++) { if (last[u]
               
                r) ans=mymax(ans,a[u]); vis[a[u]]=shen; } for (int u=L[y];u<=r;u++) { if (last[u]
                
                 r) ans=mymax(ans,a[u]); vis[a[u]]=shen; } x++; for (int u=1;u<=f[x][y][0];u++) if (vis[f[x][y][u]]!=shen) { ans=mymax(ans,f[x][y][u]); break; } return ans;}void solve (){ memset(vis,0,sizeof(vis));shen=0; int lastans=0; while (m--) { int l,r; l=read();r=read(); l=(l+lastans)%n+1;r=(r+lastans)%n+1; if (l>r) swap(l,r); lastans=solve1(l,r); printf("%d\n",lastans); }}int main(){ Ins(); prepare(); prepare1(); solve(); return 0;}