走楼梯（walk） 解题报告

时间：2024-04-20 15:07:45

走楼梯（walk）

题意

给一个长为\(n(1\le n\le 10^5)\)序列\(\{a\}\)，每次从中间挖掉\([l,r]\)，然后询问最长上升子序列，强制在线。

有一档分是30000和离线，然后考试的时候一直在莫队，发现就是不会删除....想到了离线树套树又懒得打。后来发现莫队只需要实现撤回就可以了..太菜了窝

然后我居然一直没想分块（大雾）

这里直接放原题解了，说的十分详细

年后就去刷ynoi（flag

Code:

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using std::max;

const int N=1e5+10;

const int D=320;

int a[N],b[N],pre[N],suc[N],s[N],belong[N],L[N],R[N];

int beel[D][N],beer[D][N],dewl[D][N],dewr[D][N];

int n,m,q,typ,cnt;

struct node

{

    int w,p;

    node(){}

    node(int w,int p){this->p=p,this->w=w;}

    bool friend operator <(node a,node b){return a.w==b.w?a.p>b.p:a.w<b.w;}

}yuyuyu[N],yuri[N];

void modify(int x,int d){while(x<=m)s[x]=max(s[x],d),x+=x&-x;}

int query(int x){int mx=0;while(x)mx=max(mx,s[x]),x-=x&-x;return mx;}

int main()

{

    freopen("data.in","r",stdin);

    freopen("data.out","w",stdout);

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

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

    std::sort(b+1,b+1+n);

    m=std::unique(b+1,b+1+n)-b-1;

    for(int i=1;i<=n;i++) a[i]=std::lower_bound(b+1,b+1+m,a[i])-b;

    for(int i=1;i<=n;i++)

    {

        pre[i]=query(a[i]-1)+1;

        modify(a[i],pre[i]);

    }

    for(int i=1;i<=m;i++) s[i]=0;

    for(int i=n;i;i--)

    {

        suc[i]=query(m-a[i])+1;

        modify(m+1-a[i],suc[i]);

    }

    int B=sqrt(n)+1,T=(n-1)/B+1;

    for(int i=1;i<=T;i++)

    {

        L[i]=B*(i-1)+1,R[i]=B*i<n?B*i:n;

        for(int j=L[i];j<=R[i];j++)

        {

            yuyuyu[j]=node(a[j],j);

            belong[j]=i;

        }

        std::sort(yuyuyu+L[i],yuyuyu+R[i]+1);

    }

    for(int i=1;i<=T;i++)

    {

        memcpy(beel[i],beel[i-1],sizeof beel[i]);

        for(int j=L[i];j<=R[i];j++) beel[i][a[j]]=max(beel[i][a[j]],pre[j]);

        for(int j=1;j<=m;j++) beel[i][j]=max(beel[i][j],beel[i][j-1]);

        for(int j=n;j>R[i];j--) dewl[i][j]=max(dewl[i][j+1],beel[i][a[j]-1]+suc[j]);

    }

    for(int i=T;i;i--)

    {

        memcpy(beer[i],beer[i+1],sizeof beer[i]);

        for(int j=R[i];j>=L[i];j--) beer[i][a[j]]=max(beer[i][a[j]],suc[j]);

        for(int j=m;j;j--) beer[i][j]=max(beer[i][j],beer[i][j+1]);

        for(int j=1;j<L[i];j++) dewr[i][j]=max(dewr[i][j-1],pre[j]+beer[i][a[j]+1]);

    }

    for(int i=n;i;i--) dewl[0][i]=max(dewl[0][i+1],suc[i]);

    for(int i=1;i<=n;i++) dewr[T+1][i]=max(dewr[T+1][i-1],pre[i]);

    scanf("%d",&q);

    for(int ans=0,l,r,lp,rp,i=1;i<=q;i++)

    {

        scanf("%d%d",&l,&r);

        if(typ) l^=ans,r^=ans;

        lp=belong[l],rp=belong[r];

        ans=max(dewl[lp-1][r+1],dewr[rp+1][l-1]);

        cnt=0;

        int ll=L[lp],rr=L[rp];

        while(ll<=R[lp]&&rr<=R[rp])

        {

            if(yuyuyu[ll]<yuyuyu[rr]) yuri[++cnt]=yuyuyu[ll++];

            else yuri[++cnt]=yuyuyu[rr++];

        }

        while(ll<=R[lp]) yuri[++cnt]=yuyuyu[ll++];

        while(rr<=R[rp]) yuri[++cnt]=yuyuyu[rr++];

        int c=0;

        for(int j=1;j<=cnt;j++)

        {

            int p=yuri[j].p;

            if(p<l) c=max(c,pre[p]);

            if(p>r) ans=max(ans,c+suc[p]);

        }

        printf("%d\n",ans);

    }

    return 0;

}

2019.1.11

相关文章