bzoj 4553: [Tjoi2016&Heoi2016]序列

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
 
#define ll long long
#define inf 1e9
#define eps 1e-10
#define md
#define N 100010
using namespace std;
struct QQ { int a,l,r,id,f;} q[N];
int c[N];
const int mxn=100000;
bool operator < (QQ a,QQ b) { return a.id<b.id;}
void add(int x,int d) { for (;x<=mxn;x+=x&(-x)) c[x]=max(c[x],d); }
void clear(int x) { for (;x<=mxn;x+=x&(-x)) c[x]=0;}
int query(int x)
{
	int ans=0;
	for (;x;x-=x&(-x)) ans=max(ans,c[x]);
	return ans;
}
void solve(int n,int al,int ar)
{
	if (n<1) return;
	int mid=(al+ar)>>1,w=0;
	if (al!=ar)
	{
		for (int i=1;i<=n;i++)
		  if ((al<=q[i].l&&q[i].l<=mid)||(al<=q[i].a&&q[i].a<=mid)) swap(q[i],q[++w]);
		solve(w,al,mid);
	}
	w=0;
	sort(q+1,q+n+1);
	for (int i=1;i<=n;i++)
	{
		if (q[i].l>=mid) q[i].f=max(q[i].f,query(q[i].a)+1);
		if (q[i].a<=mid) add(q[i].r,q[i].f);
	}
	for (int i=1;i<=n;i++) clear(q[i].r);
	if (al!=ar)
	{
		for (int i=1;i<=n;i++)
		  if ((mid<q[i].l&&q[i].l<=ar)||(mid<q[i].a&&q[i].a<=ar)) swap(q[i],q[++w]);
		solve(w,mid+1,ar);
	}
}
 
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&q[i].a);
		q[i].l=q[i].r=q[i].a;
		q[i].id=i; q[i].f=1;
	}
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		q[x].l=min(q[x].l,y);
		q[x].r=max(q[x].r,y);
	}
	solve(n,1,100000);
	int ans=0;
	for (int i=1;i<=n;i++) ans=max(ans,q[i].f);
	printf("%d\n",ans);
	return 0;
}