记录编号	364372	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 序列	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.278 s
提交时间	2017-01-16 10:57:17	内存使用	116.65 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
const double alpha=0.7;
struct node{
	int key,data,mx,size;
	node *ch[2];
	node(int k=1000000,int d=0):key(k),data(d),mx(d),size(1){}
	void refresh(){
		size=ch[0]->size+ch[1]->size+1;
		mx=max(data,max(ch[0]->mx,ch[1]->mx));
	}
	int cmp(int x){return x==key?-1:x>key;}
}pool[maxn*50],*null=pool,*ptr=null,*root[maxn],*nodes[maxn];
void modify(int,int,int);
int query(int,int);
node*& modify(int,int,node*&);
int query(int,node*);
void rebuild(int,int,node*&);
void travel(node*);
int n,m,a[maxn],mn[maxn],mx[maxn],x,y,cnt,tmp,ans=0;
int main(){
	freopen("heoi2016_seq.in","r",stdin);
	freopen("heoi2016_seq.out","w",stdout);
	null->size=0;
	scanf("%d%d",&n,&m);
	fill(root,root+n+1,null);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	copy(a+1,a+n+1,mn+1);
	copy(a+1,a+n+1,mx+1);
	while(m--){
		scanf("%d%d",&x,&y);
		mn[x]=min(mn[x],y);
		mx[x]=max(mx[x],y);
	}
	for(int i=1;i<=n;i++){
		tmp=query(a[i],mn[i])+1;
		ans=max(ans,tmp);
		modify(mx[i],a[i],tmp);
	}
	printf("%d",ans);
	return 0;
}
void modify(int x,int y,int d){
	while(x<=n){
		node *&rt=modify(y,d,root[x]);
		if(rt!=null){
			cnt=0;
			travel(rt);
			rebuild(1,cnt,rt);
		}
		x+=x&-x;
	}
}
int query(int x,int y){
	int ans=0;
	while(x){
		ans=max(ans,query(y+1,root[x]));
		x&=x-1;
	}
	return ans;
}
node *&modify(int x,int y,node *&rt){
	if(rt==null){
		*(rt=++ptr)=node(x,y);
		rt->ch[0]=rt->ch[1]=null;
		return null;
	}
	int d=rt->cmp(x);
	if(d==-1){
		rt->data=max(rt->data,y);
		rt->refresh();
		return null;
	}
	node *&tmp=modify(x,y,rt->ch[d]);
	rt->refresh();
	if(max(rt->ch[0]->size,rt->ch[1]->size)>rt->size*alpha)return rt;
	else return tmp;
}
int query(int x,node *rt){
	int ans=0,d;
	while(rt!=null){
		if((d=rt->key<x))ans=max(ans,max(rt->data,rt->ch[0]->mx));
		rt=rt->ch[d];
	}
	return ans;
}
void rebuild(int l,int r,node *&rt){
	if(l>r){
		rt=null;
		return;
	}
	int mid=(l+r)>>1;
	rt=nodes[mid];
	rebuild(l,mid-1,rt->ch[0]);
	rebuild(mid+1,r,rt->ch[1]);
	rt->refresh();
}
void travel(node *x){
	if(x==null)return;
	travel(x->ch[0]);
	nodes[++cnt]=x;
	travel(x->ch[1]);
}