题解- CF650D Zip-line

  • 题目意思

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

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

    先对原序列每个点做一遍以他为结束的记为，以他作为起始的记为。易得原序列的就为。

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

    对于的情况如果那就更新答案

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

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

#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]);
}