1.【题目链接】https://www.lydsy.com/JudgeOnline/problem.php?id=4358

【BZOJ4358】permu

Description

给出一个长度为n的排列P(P1,P2,...Pn)，以及m个询问。每次询问某个区间[l,r]中，最长的值域连续段长度。

Input

第一行两个整数n,m。接下来一行n个整数，描述P。接下来m行，每行两个整数l,r，描述一组询问。

Output

对于每组询问，输出一行一个整数，描述答案。

Sample Input

8 3
3 1 7 2 5 8 6 4
1 4
5 8
1 7

Sample Output

3
3
4

HINT

对于询问[1,4]，P2,P4,P1组成最长的值域连续段[1,3]；对于询问[5,8]，P8,P5,P7组成最长的值域连续段[4,6]；对于询问[1,7]，P5,P7,P3,P6组成最长的值域连续段[5,8]。1<=n,m<=50000

2.思路

若维护当前区间[l,r]中每个值向左右延伸到的最远位置（实际只要维护值域的每个边缘点向另一侧延伸的最远位置），可以O(1)转移到[l,r+1]或[l-1,r]

所以可以用特殊转移顺序的分块莫队

设块大小为B=sqrt(n)，按r从小到大分为n/B块，

对某一块r的范围为[a,a+B]，块内按l将序排序，l>a的询问满足r-l<B所以可以暴力求并撤销回空状态

对每个l<=a的询问，先转移到[l,a]，再转移到[l,r]，记录答案，撤销回到[l,a]

维护一个栈记录每次需要撤销的赋值操作以便撤销

可以保证复杂度在O((n+m)n1/2)

图中红点代表询问，橙色线代表转移顺序，灰色线代表分块

3.代码

//Happynewyear 2019/2/1 21:27
#include<bits/stdc++.h>
char buf[2000004],*ptr=buf-1;
inline int _int(){
   int x=0,c=*++ptr;
   while(c<48)c=*++ptr;
   while(c>47)x=x*10+c-48,c=*++ptr;
   return x;
}
int n,m;
int v[50050];
int ans[50050];
int ls[50050],rs[50050],mx=0;
struct Q{int l,r,id;}q[50050];
bool cmp1(Q a,Q b){return a.r<b.r;}
bool cmp2(Q a,Q b){return a.l>b.l;}
int*xs[1000000],vs[1000000],op=0;
inline void set(int*x,int v){
   xs[op]=x;
   vs[op++]=*x;
   *x=v;
}
inline void reset(int x){
   while(op>x)--op,*xs[op]=vs[op];
}
void ins(int x){
   int L=x,R=x;
   if(ls[x-1])L=ls[x-1];
   if(rs[x+1])R=rs[x+1];
   set(rs+L,R);
   set(ls+R,L);
   if(R-L+1>mx)set(&mx,R-L+1);
}
int main(){
   fread(buf,1,2000000,stdin);
   n=_int();m=_int();
   for(int i=1;i<=n;i++)v[i]=_int();
   for(int i=0;i<m;i++){
       q[i].l=_int();
       q[i].r=_int();
       q[i].id=i;
   }
   std::sort(q,q+m,cmp1);
   int B=sqrt(n+1)+1;
   int p1=0,p2=0;
   for(int i=1;;i++,p1=p2){
       int x=i*B,x0=x-B+1;
       if(x0>n)break;
       while(p2<m&&q[p2].r<=x)++p2;
       if(p1==p2)continue;
       std::sort(q+p1,q+p2,cmp2);
       while(p1<p2&&q[p1].l>x0){
           reset(0);
           int L=q[p1].l,R=q[p1].r;
           for(int j=L;j<=R;j++)ins(v[j]);
           ans[q[p1++].id]=mx;
       }
       reset(0);
       int L=x0,R=x0;
       ins(v[L]);
       while(p1<p2){
           while(L>q[p1].l)ins(v[--L]);
           int _op=op;
           for(int j=q[p1].r;j>R;j--)ins(v[j]);
           ans[q[p1++].id]=mx;
           reset(_op);
       }
   }
   for(int i=0;i<m;i++)printf("%d\n",ans[i]);
   return 0;
}