好久没写博客了..最近新学了CDQ...于是就来发一发一道CDQ的练习题
看上去就是可以dp的样子。
设(dp_{i})为以i结尾的最长不下降序列。
易得:(dp_{i})=(max(dp_{j})+1)((j<=i)&&(Max_{j}<=a_{i})&&(a_{j}<=Min_{i}))
(Max_{i})和(Min_{i})表示第i个点所有变化中的最大值和最小值。
我们考虑用一个什么东西来维护这个dp。
我的第一反应是树状数组套动态开点线段树，而且写那玩意应该也不会太长。
突然想到最近学了CDQ。
于是讲下CDQ怎么搞。
因为有两个两边不是同一个数组的条件，所以我们在solve的时候，要对([l,mid])和([mid+1,r])的根据不同的两个数组sort下，然后用个树状数组维护前缀max，算下左边对右边的贡献。
然后因为是dp，所以我们不能直接分治([l,mid])和([mid+1,r])然后合并，我们应该先分治([l,mid])然后算好([l,mid])对([mid+1,r])的贡献，然后再去分治([mid+1,r]) （记得去做([mid+1,r])前先把数组([mid+1,r])恢复）
#include<cstdio>
#include<algorithm>
#include<string>
#define ll long long
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define cross(i,k) for (register int i=first[k];i;i=last[i])
using namespace std;
inline ll read(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline ll min(ll a,ll b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}
const int N = 100010;
struct node{
int max,min,v,ans,id;
}a[N];
int n,m,x,y,ans,Max;
int c[N];
inline void Add(int x,int y){for (;x<=Max;x+=x&(-x)) c[x]=max(c[x],y);}
inline int Query(int x){int ans=0;for (;x;x-=x&(-x)) ans=max(ans,c[x]);return ans;}
inline void Clear(int x){for (;x<=Max;x+=x&(-x)) c[x]=0;}
inline bool cmp1(node a,node b){return a.max<b.max;}
inline bool cmp2(node a,node b){return a.v<b.v;}
inline bool cmp3(node a,node b){return a.id<b.id;}
inline void CDQ(int l,int r){
if (l==r) return;
int mid=l+r>>1;
CDQ(l,mid);
sort(a+l,a+mid+1,cmp1),sort(a+mid+1,a+r+1,cmp2);
int L=l,R=mid+1;
for (;L<=mid&&R<=r;R++){
for (;a[L].max<=a[R].v&&L<=mid;L++) Add(a[L].v,a[L].ans);
a[R].ans=max(a[R].ans,Query(a[R].min)+1);
}
For(i,R,r) a[i].ans=max(a[i].ans,Query(a[i].min)+1);
For(i,l,L) Clear(a[i].v);
sort(a+mid+1,a+r+1,cmp3);
CDQ(mid+1,r);
}
int main(){
n=read(),m=read();
For(i,1,n) a[i].v=a[i].max=a[i].min=read(),a[i].id=i;
For(i,1,m){
x=read(),y=read();
a[x].max=max(a[x].max,y),a[x].min=min(a[x].min,y);
}
For(i,1,n) Max=max(Max,max(a[i].v,a[i].min)),a[i].ans=1;
//For(i,1,n) printf("%d %d %d
",a[i].v,a[i].min,a[i].max);puts("");
CDQ(1,n);
For(i,1,n) ans=max(ans,a[i].ans);
//For(i,1,n) printf("%d %d %d %d
",a[i].v,a[i].min,a[i].max,a[i].ans);
printf("%d",ans);
}