bzoj 4358 permu

　　比较容易想到莫队算法+线段树，但是这样时间复杂度是O(nsqrtnlogn)无法通过，考虑如果不进行删除操作，只有添加操作的话那么并查集就可以实现了，于是可以设定sqrtn块，每个块范围为(i-1)*sqrtn到i*sqrtn,那么对于一个左端点在该块之中的询问，若右端点超过块的范围，由于右端点递增，直接添加，而询问在块中的部分则暴力添加，添加完注意还原，复杂度O(nlogn)，此题想法与CF620F有一些类似。

　　代码

 #include<cstdio>

 #include<algorithm>

 #define nc() getchar()

 #define N 500100

 #define Q 300

 using namespace std;

 int n,m,i,j,k,pos[N],ans,Ans[N],tmp,top,stack[N];

 inline int read(){

     int x=;char ch=nc();for(;ch<''||ch>'';ch=nc());

     for(;ch<=''&&ch>='';x=x*+ch-,ch=nc());return x;

 }

 struct g{

     int l,r,id;

 }a[N];

 int f[N],s[N],e[N];

 bool cmp(g a,g b)

 {

     if (pos[a.id]==pos[b.id])

     return a.r<b.r;

     return pos[a.id]<pos[b.id];

 }

 int gf(int x)

 {

     int p=x,t;

     while (p!=f[p]) p=f[p];

     while (x!=p) t=f[x],f[x]=p,x=t;

     return p;

 }

 int GF(int x){

     int p=x;

     while (p!=f[p]) p=f[p];return p;

 }

 void add(int x)

 {

     s[x]=;

     int a,b;

     a=gf(x+);b=gf(x-);

     if (s[a]) s[a]+=s[gf(x)],f[gf(x)]=a;

     if (s[b]) s[b]+=s[gf(x)],f[gf(x)]=b;

     ans=max(ans,s[gf(x)]);

 }

 void add2(int x)

 {

     s[x]=;

     int a,b;

     a=GF(x+);b=GF(x-);

     if (s[a])

     {

         s[GF(x)]+=s[a];f[a]=GF(x);

         top++;stack[top]=a;

     }

     if (s[b])

     {

         s[GF(x)]+=s[b];f[b]=GF(x);

         top++;stack[top]=b;

     }

     ans=max(ans,s[x]);

 }

 int main()

 {

     n=read();

     m=read();

     for (i=;i<=n;i++)

         e[i]=read();

     for (i=;i<=m;i++)

     {

         a[i].l=read();

         a[i].r=read();

         a[i].id=i;

         pos[i]=a[i].l/Q;

     }

     sort(a+,a++m,cmp);

     for (i=;i<=m;i++)

     {

         int cur=(a[i].l/Q+)*Q;

         int now=min(n+,cur);

         for (k=i;k<=m;k++) if (a[k].l/Q!=a[i].l/Q) break;

         int o=k;

         for (j=;j<=n+;j++) f[j]=j,s[j]=;ans=;

         for (j=i;j<o;j++)

         {

             while (cur<=a[j].r) add(e[cur++]);

             tmp=ans;top=;

             for (k=a[j].l;k<=min(a[j].r,now-);k++)

                 add2(e[k]);

             Ans[a[j].id]=ans;

             for (k=top;k>=;k--) f[stack[k]]=stack[k];

             for (k=a[j].l;k<=min(a[j].r,now-);k++)

                 s[e[k]]=,f[e[k]]=e[k];

             ans=tmp;

         }

         i=o-;

     }

     for (i=;i<=m;i++)

     printf("%d\n",Ans[i]);

 }