这道题原来很水的？

noteskey

一开始以为是顺序的 m 个修改，然后选出一段最长子序列使得每次修改后都满足不降

这 TM 根本不可做啊！ 于是就去看题解了，然后看到转移要满足的条件的我发出了黑人问号...

然后才发现原来是求的子序列是满足任意一次修改后不降...

于是列出两（san）个条件式子，就可以 CDQ 切掉了 QWQ

\(j<i\)

\(a_j<min_i\)

\(max_j<a_i\)

这里的 max 和 min 就是某个位置上出现过的最 大/小 值

watch out

需要注意的就是 CDQ 先处理左半部分再处理当前部分再处理右半部分，否则左半部分对右半部分的贡献就会出锅

还有就是看清楚题目，别交错题，我就是那个交错题 RE 了十几次的...

code

可能某个合并还有优化的空间？【雾

//by Judge

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const int M=1e5+3;

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline bool cmax(int& a,int b){return a<b?a=b,1:0;}

inline bool cmin(int& a,int b){return a>b?a=b,1:0;}

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} int n,m,p,ans,f[M],c[M];

struct node{ int x,l,r,id;

	inline void init(int iid){

		x=l=r=read(),id=iid,cmax(p,x);

	}

}a[M];

inline bool cmpx(node& a,node& b){return a.x<b.x;}

inline bool cmpl(node& a,node& b){return a.l<b.l;}

inline bool cmpid(node& a,node& b){return a.id<b.id;}

inline void clear(int x){for(;x<=p;x+=x&-x) c[x]=0;}

inline void update(int x,int d){for(;x<=p;x+=x&-x) cmax(c[x],d);}

inline int query(int x,int s=0){for(;x;x^=x&-x) cmax(s,c[x]);return s;}

void CDQ(int l,int r){ if(l==r) return ; int mid=(l+r)>>1;

	CDQ(l,mid),sort(a+l,a+1+mid,cmpx),sort(a+1+mid,a+1+r,cmpl);

	Rg int i=l,j=mid+1;

	for(;j<=r;++j){

		while(i<=mid&&a[i].x<=a[j].l)

			update(a[i].r,f[a[i].id]),++i;

		cmax(f[a[j].id],query(a[j].x)+1);

	}

	while(i>l) --i,clear(a[i].r); j=r,i=l;

	sort(a+l,a+1+r,cmpid);

	CDQ(mid+1,r);

}

int main(){ n=read(),m=read(); Rg int x,y;

	fp(i,1,n) a[i].init(i),f[i]=1;

	fp(i,1,m) x=read(),y=read(),

		cmin(a[x].l,y),cmax(a[x].r,y);

	CDQ(1,n); fp(i,1,n) cmax(ans,f[i]);

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

}