题解 CF650D 【Zip-line】

奇米 · 2020-01-20 10:30:36 · 题解

题解- CF650D Zip-line

• 题目意思

  就是给你个序列以及多次操作，每次把ai换做bi求一遍lis（操作之间互不影响）

  • Sol

  显然每次修改暴力做lis是不可行的复杂度至少为O(n^2 \log n )。于是我们要思考每次修改会对答案形成怎样的影响。

  先对原序列每个点做一遍以他为结束的lis记为fi，以他作为起始的lis记为gi。易得原序列的lis就为max\{fi+gi-1\}。

  每次对于修改一个值分几种情况来考虑 （思路借鉴 霜雪谦年 的题解），我们记修改过后的fi为fi'，gi'同理。

  对于+1的情况如果fi'+gi'+1>ans那就更新答案

  对于-1的情况相对复杂一点。我们要先判断此次修改的点是否为原序列lis的必经之点，判断的方法很简单如果fi+gi-1=ans，并且这样的情况有且只有一种。

  剩余的就是不变的情况了。于是我们这道题目就做完了。求lis可以使用树状数组来实现fi正着gi倒着即可并且要离散化一下就可以了。用离线来实现。

  • Code

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

const int N=800005;

int n,m,ans,f[N],g[N],tr[N];
int a[N],b[N],res[N],cs[N],cnt;

struct number {
    int id,x,val;
    int f,g;
    inline bool friend operator < (const number &a,const number &b) {
        if(a.x==b.x) return a.val<b.val;
        return a.x<b.x;
    }
};
number q[N];

inline int read() {
    int sum=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) 
        sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

inline void jia(int x,int v) {
    while(x<=cnt) {
        tr[x]=max(tr[x],v);
        x+=lowbit(x);
    }
}

inline int query(int x) {
    int ret=0;
    while(x) {
        ret=max(ret,tr[x]);
        x-=lowbit(x);
    }
    return ret;
}

int main() {
    n=read(),m=read();
    cnt=n;
    for ( int i=1;i<=n;i++ ) {
        a[i]=read();
        b[i]=a[i];
    }
    for ( int i=1;i<=m;i++ ) {
        q[i].id=i;
        q[i].x=read();
        q[i].val=read();
        b[++cnt]=q[i].val;
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for ( int i=1;i<=n;i++ ) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    for ( int i=1;i<=m;i++ ) q[i].val=lower_bound(b+1,b+cnt+1,q[i].val)-b;
    for ( int i=1;i<=n;i++ ) {
        f[i]=query(a[i]-1)+1;
        jia(a[i],f[i]);
    }
    memset(tr,0,sizeof(tr));
    for ( int i=n;i>=1;i-- ) {
        g[i]=query(cnt-a[i])+1;
        jia(cnt-a[i]+1,g[i]);
    }
    for ( int i=1;i<=n;i++ ) ans=max(ans,f[i]+g[i]-1);
    for ( int i=1;i<=n;i++ ) if(f[i]+g[i]-1==ans) cs[f[i]]++;
    sort(q+1,q+m+1);
    memset(tr,0,sizeof(tr));
    int now=1;
    for ( int i=1;i<=m;i++ ) {
        while(now<q[i].x) {
            jia(a[now],f[now]);
            now++;
        }
        q[i].f=query(q[i].val-1);
    }
    memset(tr,0,sizeof(tr));
    now=n;
    for ( int i=m;i>=1;i-- ) {
        while(now>q[i].x) {
            jia(cnt-a[now]+1,g[now]);
            now--;
        }
        q[i].g=query(cnt-q[i].val);
        if(q[i].f+q[i].g+1>ans) res[q[i].id]=q[i].f+q[i].g+1;
    }
    for ( int i=1;i<=m;i++ ) if(!res[q[i].id]) {
        if(f[q[i].x]+g[q[i].x]==ans+1&&cs[f[q[i].x]]==1&&q[i].f+q[i].g+1<ans) res[q[i].id]=ans-1;
        else res[q[i].id]=ans;
    }
    for ( int i=1;i<=m;i++ ) printf("%d\n",res[i]);
}