luogu4093 序列

这个题首先考虑的算法肯定是dp了(如果数据不毒瘤的话)

    f[0]=0;ans=0;
    for (rint i=1;i<=n;i++)
        for (rint j=0;j<=i-1;j++)
            if (minn[i]>=a[j] && maxx[j]<=a[i])
                f[i]=max(f[i],f[j]+1);
    for (rint i=1;i<=n;i++) ans=max(ans,f[i]);
    cout<<ans;

当然这个题既然让你树套树，你就肯定得树套树……显然这个O(n2)的DP会爆掉…… 因为我们树套树只学过怎么二维数点，而前面又有正好两个表达式——对于点i，可以转移过来的点j必须满足三个式子

1<=j<=i

a[j]<=minn[i]

maxx[j]<=a[i]

所以我现在有一个思路：用扫描线去掉第一维，剩下的线段树套线段树，外层的下标是a[j]，内层的的下标是maxx[j]，维护的是f[i]的最大值，这样我们就可以现在外层查询(1,minn[i])以内的点，内层查(1,a[i])以内，查到的就是满足这两个条件的最大的f[j]，记为ans。我们可以再写一个这样的dp方程，f[i]=ans+1;

那么我们再看复杂度，树套树是(log2n)，扫描线是(n)，相乘就是(nlog2n)，考虑时限两秒，完全可以应付。 等等，这TM是正解？我竟然推出来了？

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
#define big 1e9
#define maxn 100010
#define mid (l+r>>1)
using namespace std;
int f[maxn],a[maxn],minn[maxn],maxx[maxn];
int n,m,cnt,rt;
ini read()
{
	char c;int r=0,f=1;
	while (c<'0' || c>'9')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9')
	{
		r=r*10+c-'0';
		c=getchar();
	}
	return r*f;
}
struct IN_node
{
	int val,ls,rs;
}in[maxn<<7];
struct OUT_node
{
	int pos,ls,rs;
}out[maxn<<2];
inv build(int l,int r,int &num)
{
	if (!num) num=++cnt;
	if (l==r) return;
	build(l,mid,out[num].ls);
	build(mid+1,r,out[num].rs);
}
inv changeY(int l,int r,int &num,int x,int c)
{
	if (!num) num=++cnt;
	in[num].val=max(in[num].val,c);
	if (l==r) return;
	if (x<=mid) changeY(l,mid,in[num].ls,x,c);
	else changeY(mid+1,r,in[num].rs,x,c);
}
inv changeX(int l,int r,int num,int x,int y,int c)
{
	changeY(1,maxn,out[num].pos,y,c);
	if (l==r) return;
	if (x<=mid) changeX(l,mid,out[num].ls,x,y,c);
	else changeX(mid+1,r,out[num].rs,x,y,c);
}
ini queryY(int L,int R,int l,int r,int num)
{
	if (!num) return 0;
	if (L<=l && r<=R) return in[num].val;
	int res=0;
	if (L<=mid) res=max(res,queryY(L,R,l,mid,in[num].ls));
	if (R>mid) res=max(res,queryY(L,R,mid+1,r,in[num].rs));
	return res;
}
ini queryX(int l,int r,int num,int L1,int R1,int L2,int R2)
{
	if (L1<=l && r<=R1) return queryY(L2,R2,1,maxn,out[num].pos);
	//      zz错误↑↑                           zz错误之二↑↑ 
	int res=0;
	if (L1<=mid) res=max(res,queryX(l,mid,out[num].ls,L1,R1,L2,R2)); 
	if (R1>mid) res=max(res,queryX(mid+1,r,out[num].rs,L1,R1,L2,R2));
	return res;
}
int main()
{
	n=read();m=read();
	for (rint i=1;i<=n;i++) 
	{
		a[i]=read();
		minn[i]=maxx[i]=a[i];
	}
	for (rint i=1;i<=m;i++)
	{
		int x,y;x=read();y=read();
		if (minn[x]>y) minn[x]=y;
		if (maxx[x]<y) maxx[x]=y;
	}
	build(1,maxn,rt);
	int ans=0;
	for (rint i=1;i<=n;i++)
	{
		f[i]=queryX(1,maxn,rt,1,minn[i],1,a[i])+1;
		changeX(1,maxn,rt,a[i],maxx[i],f[i]);
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
} 

序列解题报告

树套树入门题

luogu4093 序列