由于序列在一时刻下只有一种变化,也就意味着最多只有一个数发生了变化。

预处理每一个数的最大值 $r_i$ ,最小值 $l_i$ ,以及原有的值 $v_i$ ,也只有这些值会产生贡献。

那么方程为

$f_i=\max\limits_{j<i,r_j\le v_i,v_j\le l_i}\{f_j+1\}$

打一发暴力,T了。

观察一下发现是一个三维偏序,打一发cdq即可。

注意处理顺序。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define gc getchar()
#define ll long long
#define eps 1e-8
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=12e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int l,r,v,id;}q[N];
inline bool cmpr(node a,node b){return a.r<b.r;}
inline bool cmpv(node a,node b){return a.v<b.v;}
inline bool cmpid(node a,node b){return a.id<b.id;}
int c[N],mx,f[N],n,m;
inline void add(int x,int v){for(;x<=mx;x+=x&-x)c[x]=max(c[x],v);}
inline void clear(int x){for(;x<=mx;x+=x&-x)c[x]=0;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans=max(ans,c[x]);return ans;}
void cdqdiv(int l,int r)
{
    if(l==r)return ;
    int mid=l+r>>1,j=l,i=mid+1;
    cdqdiv(l,mid);
    sort(q+j,q+i,cmpr);sort(q+i,q+r+1,cmpv);
    while(i<=r)
    {
        while(j<=mid&&q[j].r<=q[i].v)
            add(q[j].v,f[q[j].id]),++j;
        f[q[i].id]=max(f[q[i].id],ask(q[i].l)+1);++i;
    }
    for(j--;j>=l;j--)clear(q[j].v);
    sort(q+mid+1,q+r+1,cmpid);
    cdqdiv(mid+1,r);
}
int main()
{
    freopen("seq1.in","r",stdin);
    qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(q[i].v),q[i].l=q[i].r=q[i].v,q[i].id=i,f[i]=1,mx=max(mx,q[i].v);
    for(int i=1,x,y;i<=m;i++)qr(x),qr(y),q[x].l=min(y,q[x].l),q[x].r=max(y,q[x].r),mx=max(mx,y);
    cdqdiv(1,n);int ans=1;
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    qw(ans);puts("");
    return 0;
}