「TJOI/HEOI2016」序列 - CDQ分治三维偏序 / 树套树

题目大意

    佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。
    现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。
    注意：每种变化最多只有一个值发生变化。
    在样例输入1中，所有的变化是：

1 2 3
2 2 3
1 3 3
1 1 3
1 2 4

    选择子序列为原序列，即在任意一种变化中均为不降子序列
    在样例输入2中，所有的变化是:

3 3 3
3 2 3

    选择子序列为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要求。

---

题目分析

开始读错题了。

可以将原题转化为序列DP：

$$f(i)=f(j)+1\quad(j\le i,Max(j)\le a(i),a(j)\le Min(i))$$

然后这就是一个三维偏序的模板。
直接上CDQ分治或者树套树即可。

---

代码

#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=100005,maxv=100000;

struct Segment_Tree {
	struct Tree {
		int ls,rs,max;
	} tree[maxn*100];
	int size;
#define mid ((left+right)>>1)
	void modify(int &index,int left,int right,int tar,int val) {
		if(!index)index=++size;
		tree[index].max=max(tree[index].max,val);
		if(left==right)return;
		if(tar<=mid)modify(tree[index].ls,left,mid,tar,val);
		else modify(tree[index].rs,mid+1,right,tar,val);
	}
	int query(int index,int left,int right,int Left,int Right) {
		if(!index||Right<left||Left>right)return 0;
		if(Left<=left&&Right>=right)return tree[index].max;
		return max(query(tree[index].ls,left,mid,Left,Right),query(tree[index].rs,mid+1,right,Left,Right));
	}
} st;

int n,m,a[maxn],f[maxn],Min[maxn],Max[maxn];

struct BIT {
	int root[maxn];
#define lowbit(x) x&(-x)
	void modify(int id) {
		for(int i=a[id]; i<=maxv; i+=lowbit(i))st.modify(root[i],1,maxv,Max[id],f[id]);
	}
	int query(int id) {
		int ans=0;
		for(int i=Min[id]; i>=1; i-=lowbit(i))ans=max(ans,st.query(root[i],1,maxv,1,a[id]));
		return ans;
	}
} bit;

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)Max[i]=Min[i]=a[i]=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),v=Get_Int();
		Max[x]=max(Max[x],v);
		Min[x]=min(Min[x],v);
	}
	int ans=0;
	for(int i=1; i<=n; i++) {
		f[i]=bit.query(i)+1;
		ans=max(ans,f[i]);
		bit.modify(i);
	}
	printf("%d\n",ans);
	return 0;
}