记录编号	367492	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 序列	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.967 s
提交时间	2017-01-30 22:27:12	内存使用	15.55 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4e5+10;
int n,m,a[N],d[N],l[N],r[N],ans[N];
#define lc x<<1
#define rc x<<1|1
int Max[N];
void change(int x,int l,int r,int p,int d){
	if (l==r){Max[x]=max(Max[x],d);return;}
	int mid=(l+r)>>1;
	if (p>mid) change(rc,mid+1,r,p,d);
		else change(lc,l,mid,p,d);
	Max[x]=max(Max[lc],Max[rc]);
}
void clear(int x,int l,int r,int p){
	Max[x]=0;
	if (l==r) return;
	int mid=(l+r)>>1;
	if (p>mid) clear(rc,mid+1,r,p);
		else clear(lc,l,mid,p);
}
int getmax(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return Max[x];
	int mid=(l+r)>>1,ans=0;
	if (R>mid) ans=max(ans,getmax(rc,mid+1,r,L,R));
	if (L<=mid) ans=max(ans,getmax(lc,l,mid,L,R));
	return ans;
}
struct opt{int id,x,y,tp;}Q[N];
//tp=1表示只算贡献,tp=0表示只计算答案 
bool cmp(const opt &x,const opt &y){
	return x.x==y.x?x.tp>y.tp:x.x<y.x;
}
void solve(int L,int R){
	if (L==R) return;
	int mid=(L+R)>>1,cnt=0;
	solve(L,mid);
	for (int i=L;i<=mid;i++)
		Q[++cnt]=(opt){i,a[i],r[i],1};
	for (int i=mid+1;i<=R;i++)
		Q[++cnt]=(opt){i,l[i],a[i],0};
	sort(Q+1,Q+cnt+1,cmp);
	for (int i=1;i<=cnt;i++){
		if (Q[i].tp) change(1,1,1e5,Q[i].y,ans[Q[i].id]);
			else ans[Q[i].id]=max(ans[Q[i].id],getmax(1,1,1e5,1,Q[i].y)+1);
	}
	for (int i=1;i<=cnt;i++)
		if (Q[i].tp) clear(1,1,1e5,Q[i].y);
	solve(mid+1,R);
}
int main()
{
	freopen("heoi2016_seq.in","r",stdin);
	freopen("heoi2016_seq.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]),l[i]=r[i]=a[i];
	for (int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		l[x]=min(l[x],y);
		r[x]=max(r[x],y);
	}
	ans[1]=1;solve(1,n);
	int Ans=0;
	for (int i=1;i<=n;i++) Ans=max(Ans,ans[i]);
	printf("%d\n",Ans);
	return 0;
}