记录编号	358162	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 序列	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	1.590 s
提交时间	2016-12-14 18:38:25	内存使用	17.08 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010<<2;
int n,m,f[maxn],low[maxn],c[maxn],H;
struct Rabit_q{int t,u,d,a;}q[maxn],tmp[maxn];
bool Rabit_compl(Rabit_q a,Rabit_q b){return a.u<b.u;}
bool Rabit_compr(Rabit_q a,Rabit_q b){return a.a<b.a;}
void Rabit_max(int &x,int y){if(x<y)x=y;}
void Rabit_min(int &x,int y){if(x>y)x=y;}
void Rabit_in(){
	scanf("%d%d",&n,&m);int i,x,y;
	for(i=1;i<=n;i++)q[i].t=i,scanf("%d",&q[i].a),q[i].u=q[i].d=q[i].a,f[i]=1;
	for(i=1;i<=m;i++)
		scanf("%d%d",&x,&y),Rabit_max(q[x].u,y),Rabit_min(q[x].d,y);
	for(i=1;i<=n;i++)Rabit_max(H,q[i].d);
	for(i=1;i<=H;i++)low[i]=i&(-i);
	//printf("%d %d %d\n",H,n,m);
}
void Rabit_dig(int i,int x){
	for(;i<=H;i+=low[i])Rabit_max(c[i],x);
}
int Rabit_get(int i){
	int res=0;for(;i;i-=low[i])Rabit_max(res,c[i]);return res;
}
void Rabit_del(int i){
	for(;i<=H&&c[i];i+=low[i])c[i]=0;
}
void Rabit_run(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1,i,j;
	Rabit_run(l,mid);
	for(i=l;i<=r;i++)tmp[i]=q[i];
	sort(tmp+l,tmp+mid+1,Rabit_compl);
	sort(tmp+mid+1,tmp+r+1,Rabit_compr);
	i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(tmp[i].u<=tmp[j].a)Rabit_dig(tmp[i].a,f[tmp[i].t]),i++;
		else Rabit_max(f[tmp[j].t],Rabit_get(tmp[j].d)+1),j++;
	}
	while(j<=r)
		Rabit_max(f[tmp[j].t],Rabit_get(tmp[j].d)+1),j++;
	//memset(c,0,sizeof(c));
	for(j=l;j<i;j++)Rabit_del(tmp[j].a);
	Rabit_run(mid+1,r);
}
int main(){
	freopen("heoi2016_seq.in","r",stdin);freopen("heoi2016_seq.out","w",stdout);
	Rabit_in();Rabit_run(1,n);
	int Ans=0;
	for(int i=1;i<=n;i++)if(f[i]>Ans)Ans=f[i];
	printf("%d\n",Ans);
	fclose(stdin),fclose(stdout);
	return 0;
}