【题意】给定长度为n的排列，m次询问区间[L,R]的最长连续值域。n<=50000。

【算法】莫队算法

【题解】考虑莫队维护增加一个数的信息：设up[x]表示数值x往上延伸的最大长度，down[x]表示数值x往下延伸的最大长度。

增加一个数x时，up[x]=up[x+1]+1,down[x]=down[x-1]+1。令t=up[x]+down[x]+1，可以用于更新答案。

同时，增加x后会影响到x所在连续区间最大数和最小数，中间的数字不会影响后面的答案（因为只考虑加数，中间的数字虽然改变但不会被调用），所以有：

down[x+up[x]-1] = up[x-down[x]+1] = t

回顾莫队算法的复杂度分析。莫队算法按左端点分块，块内按右端点排序。假设块大小为B，左端点复杂度O(B*q)，右端点复杂度O(n/B*n)。

实际上，我们只需要保证每次询问左端点复杂度为O(B)，每一块询问右端点复杂度为O(n)就可以了。

既然只需要每次询问左端点复杂度为O(B)，干脆不用删点的操作实现，改成暴力加点实现。

记块的右端点的r，对于同一块的询问，将>r的右端点逐渐增加向右扩展并累计。对于每次询问，暴力增加块内的部分至询问左端点处，用栈记录修改，做完后清除。

复杂度O(n√m)。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=50010;int a[maxn],ANS[maxn],s1[maxn*2],s2[maxn*2],up[maxn],down[maxn],top,ans,answer;int n,m;struct cyc{
    int l,r,q,id;}b[maxn];bool cmp(cyc x,cyc y){
    return x.q^y.q?x.q
          
           
            r)modify(a[++r]); top=0;//forget... answer=ans=max(answer,ans); for(int j=b[i].l;j<=min(t,b[i].r);j++)modify(a[j]); ANS[b[i].id]=ans; for(int j=top;j>=1;j--)if(j%2)down[s1[j]]=s2[j];else up[s1[j]]=s2[j]; for(int j=b[i].l;j<=min(t,b[i].r);j++)up[a[j]]=down[a[j]]=0; } for(int i=1;i<=m;i++)printf("%d\n",ANS[i]); return 0;}
           
          
         
        
       
      

 

注意：栈数组开2倍

还有想着后面要记得写的东西可以先写到草稿纸上，不然后面忘了……GG