【BZOJ】4358: permu 莫队算法

【题意】给定长度为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<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int a[maxn],ANS[maxn],s1[maxn*],s2[maxn*],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<y.q:x.r<y.r;}

void modify(int x){

    up[x]=up[x+]+;

    down[x]=down[x-]+;

    int t=up[x]+down[x]-;

    s1[++top]=x+up[x]-;s2[top]=down[s1[top]];

    s1[++top]=x-down[x]+;s2[top]=up[s1[top]];

    down[s1[top-]]=up[s1[top]]=t;

    ans=max(ans,t);

}

int main(){

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

    int Q=(int)(1.0*n/sqrt(m));

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

    for(int i=;i<=m;i++){scanf("%d%d",&b[i].l,&b[i].r);b[i].q=(b[i].l-)/Q+;b[i].id=i;}

    sort(b+,b+m+,cmp);

    int r=,t=;

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

        if(b[i].q!=b[i-].q){

            memset(up,,sizeof(up));

            memset(down,,sizeof(down));

            t=r=b[i].q*Q;answer=;

        }

        ans=;top=;

        while(b[i].r>r)modify(a[++r]);

        top=;//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>=;j--)if(j%)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]]=;

    }

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

    return ;

}

注意：栈数组开2倍

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