bzoj 4358: permu 莫队

　　第一步先莫队分块。

　　对于每一块l~r，初始右端点设为r+1，然后每个询问先将右端点往右移，然后处理询问在l~r之间的部分，最后用一个栈再把l~r的复原。

　　具体来说是维护两个数组now1和now2，一个向右最长的长度，一个向左的长度，每插入一个值x，用x+1的now2更新x的now2，用x-1的now1更新x的now1，now1[x]+now2[x]-1可能为最终答案，再把x所在的最长区间的左右端点的now数组更新，中间的值不需要更新，因为不可能再往中间插入数了。

　　有生以来第一次bzoj榜一。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define N 50005

 #define d 223

 using namespace std;

 int n,m;

 int c[N];

 int ans[N];

 struct node

 {

     int l,r,id,yuan;

     friend bool operator < (node aa,node bb)

     {

         if(aa.id!=bb.id)return aa.id<bb.id;

         return aa.r<bb.r;

     }

 }a[N];

 int now1[N],now2[N];

 int st1[N*],st2[N*],top;

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)scanf("%d",&c[i]);

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

     {

         scanf("%d%d",&a[i].l,&a[i].r);

         a[i].yuan=i;a[i].id=(a[i].l-)/d+;

     }

     sort(a+,a+m+);

     int as=;int r=,t=;

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

     {

         if(a[i].id!=a[i-].id)

         {

             as=;

             memset(now1,,sizeof(now1));

             memset(now2,,sizeof(now2));

             r=t=a[i].id*d;

         }

         while(a[i].r>r)

         {

             r++;

             now1[c[r]]=now1[c[r]+]+;

             now2[c[r]]=now2[c[r]-]+;

             int tt=now1[c[r]]+now2[c[r]]-;

             now2[c[r]+now1[c[r]]-]=tt;

             now1[c[r]-now2[c[r]]+]=tt;

             as=max(as,tt);

         }

         int tmp=as;top=;

         for(int j=a[i].l;j<=min(a[i].r,t);j++)

         {

             now1[c[j]]=now1[c[j]+]+;

             now2[c[j]]=now2[c[j]-]+;

             int tt=now1[c[j]]+now2[c[j]]-;

             int rr=c[j]+now1[c[j]]-;int ll=c[j]-now2[c[j]]+;

             st1[++top]=rr;st2[top]=now2[rr];

             st1[++top]=ll;st2[top]=now1[ll];

             now2[rr]=tt;

             now1[ll]=tt;

             tmp=max(tmp,tt);

         }

         for(int j=top;j>=;j--)

         {

             if(j%==)now1[st1[j]]=st2[j];

             else now2[st1[j]]=st2[j];

         }

         for(int j=a[i].l;j<=min(a[i].r,t);j++)

         {

             now1[c[j]]=now2[c[j]]=;

         }

         ans[a[i].yuan]=tmp;

     }

     for(int i=;i<=m;i++)printf("%d\n",ans[i]);

     return ;

 }

巴特西

bzoj 4358: permu 莫队

最新文章

热门文章