bzoj 4358 permu

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

　　代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define nc() getchar()
  4 #define N 500100
  5 #define Q 300
  6 using namespace std;
  7 int n,m,i,j,k,pos[N],ans,Ans[N],tmp,top,stack[N];
  8 inline int read(){
  9     int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
 10     for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
 11 }
 12 struct g{
 13     int l,r,id;
 14 }a[N];
 15 int f[N],s[N],e[N];
 16 bool cmp(g a,g b)
 17 {
 18     if (pos[a.id]==pos[b.id])
 19     return a.r<b.r;
 20     return pos[a.id]<pos[b.id];
 21 }
 22 int gf(int x)
 23 {
 24     int p=x,t;
 25     while (p!=f[p]) p=f[p];
 26     while (x!=p) t=f[x],f[x]=p,x=t;
 27     return p;
 28 }
 29 int GF(int x){
 30     int p=x;
 31     while (p!=f[p]) p=f[p];return p;
 32 }
 33 void add(int x)
 34 {
 35     s[x]=1;
 36     int a,b;
 37     a=gf(x+1);b=gf(x-1);
 38     if (s[a]) s[a]+=s[gf(x)],f[gf(x)]=a;
 39     if (s[b]) s[b]+=s[gf(x)],f[gf(x)]=b;
 40     ans=max(ans,s[gf(x)]);
 41 }
 42 void add2(int x)
 43 {
 44     s[x]=1;
 45     int a,b;
 46     a=GF(x+1);b=GF(x-1);
 47     if (s[a]) 
 48     {
 49         s[GF(x)]+=s[a];f[a]=GF(x);
 50         top++;stack[top]=a;
 51     }
 52     if (s[b]) 
 53     {
 54         s[GF(x)]+=s[b];f[b]=GF(x);
 55         top++;stack[top]=b;
 56     }
 57     ans=max(ans,s[x]);
 58 }
 59 int main()
 60 {
 61     n=read();
 62     m=read();
 63     for (i=1;i<=n;i++)
 64         e[i]=read();
 65     for (i=1;i<=m;i++)
 66     {
 67         a[i].l=read();
 68         a[i].r=read();
 69         a[i].id=i;
 70         pos[i]=a[i].l/Q;
 71     }
 72 
 73     sort(a+1,a+1+m,cmp);
 74     for (i=1;i<=m;i++)
 75     {
 76         int cur=(a[i].l/Q+1)*Q;
 77         int now=min(n+1,cur);
 78         for (k=i;k<=m;k++) if (a[k].l/Q!=a[i].l/Q) break;
 79         int o=k;
 80         for (j=0;j<=n+1;j++) f[j]=j,s[j]=0;ans=0;
 81     
 82         for (j=i;j<o;j++)
 83         {    
 84             while (cur<=a[j].r) add(e[cur++]);
 85             tmp=ans;top=0;
 86                 
 87             for (k=a[j].l;k<=min(a[j].r,now-1);k++)
 88                 add2(e[k]);
 89             
 90             Ans[a[j].id]=ans;
 91         
 92             for (k=top;k>=1;k--) f[stack[k]]=stack[k];
 93             for (k=a[j].l;k<=min(a[j].r,now-1);k++)
 94                 s[e[k]]=0,f[e[k]]=e[k];    
 95             ans=tmp;
 96         
 97         }
 98         
 99         i=o-1;
100     }
101     
102     for (i=1;i<=m;i++)
103     printf("%d
",Ans[i]);
104 }