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

【BZOJ4358】permu

Description

給出一個長度為n的排列P(P1,P2,...Pn)，以及m個詢問。每次詢問某個區(qū)間[l,r]中，最長的值域連續(xù)段長度。

Input

第一行兩個整數(shù)n,m。接下來一行n個整數(shù)，描述P。接下來m行，每行兩個整數(shù)l,r，描述一組詢問。

Output

對于每組詢問，輸出一行一個整數(shù)，描述答案。

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組成最長的值域連續(xù)段[1,3]；對于詢問[5,8]，P8,P5,P7組成最長的值域連續(xù)段[4,6]；對于詢問[1,7]，P5,P7,P3,P6組成最長的值域連續(xù)段[5,8]。1<=n,m<=50000

2.思路

若維護當前區(qū)間[l,r]中每個值向左右延伸到的最遠位置（實際只要維護值域的每個邊緣點向另一側(cè)延伸的最遠位置），可以O(shè)(1)轉(zhuǎn)移到[l,r+1]或[l-1,r]

所以可以用特殊轉(zhuǎn)移順序的分塊莫隊

設(shè)塊大小為B=sqrt(n)，按r從小到大分為n/B塊，

對某一塊r的范圍為[a,a+B]，塊內(nèi)按l將序排序，l>a的詢問滿足r-l<B所以可以暴力求并撤銷回空狀態(tài)

對每個l<=a的詢問，先轉(zhuǎn)移到[l,a]，再轉(zhuǎn)移到[l,r]，記錄答案，撤銷回到[l,a]

維護一個棧記錄每次需要撤銷的賦值操作以便撤銷

可以保證復(fù)雜度在O((n+m)n1/2)

圖中紅點代表詢問，橙色線代表轉(zhuǎn)移順序，灰色線代表分塊

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;
}