题解 bzoj3688【折线统计】

考虑 \(dp\) 。

首先把所有节点按 \(x\) 从小到大排序是很有必要的。

记 f[i][j][0] 表示满足以第 \(i\) 个节点做折线结尾，选取的点集 \(S\) 满足 \(f(S)=j\) ，且最后一段折线指向右上 \((↗)\) 的方案数。

记 f[i][j][1] 表示满足以第 \(i\) 个节点做折线结尾，选取的点集 \(S\) 满足 \(f(S)=j\) ，且最后一段折线指向右下 \((↘)\) 的方案数。

状态转移方程：（我觉得挺显然的，感性理解一下就行了

\[f[i][j][0]=\sum\limits_{i'<i \ \& \ y[i']<y[i]} f[i'][j][0]+\sum\limits_{i'<i \ \& \ y[i']<y[i]} f[i'][j-1][1]
\]

\[f[i][j][1]=\sum\limits_{i'<i \ \& \ y[i']>y[i]} f[i'][j][1] + \sum\limits_{i'<i \ \& \ y[i']>y[i]} f[i'][j-1][0]
\]

答案即为 \(\sum f[i][k][0]+\sum f[i][k][1]\) 。

然后我们发现直接这样做 \(dp\) 是 \(Θ(n^2k)\) 的。

\(...\)

其实我们可以发现：

这个 \(i'<i\) 的限制按照 \(x\) 从小到大扫描的顺序就可以解决。

这个 \(y[i']<y[i]\) 以及 \(y[i']>y[i]\) 的限制可以用一个数据结构（线段树 \(/\) 树状数组）优化成 \(\log\) 。

时间复杂度 \(Θ(n \ k \log n)\) 。

Code 部分

#include<cstdio>

#include<algorithm>

#define RI register int

using namespace std;

inline int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

const int SIZE=50010,M=21,MAXV=100000;

const int mod=1e5+7;

int n,m;

struct Node{

	int x,y;

}a[SIZE];

int cmp(Node a,Node b)

{

	return a.x<b.x;

}

int c[M][MAXV+100][2];

void add(int d1,int x,int d2,int val)

{

	for(;x<=MAXV;x+=x&-x)c[d1][x][d2]=(c[d1][x][d2]+val)%mod;

}

int ask(int d1,int d2,int x)

{

	int ans=0;

	for(;x;x-=x&-x)ans=(ans+c[d1][x][d2])%mod;

	return ans;

}

int query(int d1,int d2,int l,int r)

{

	if(l>r)return 0;

	int ans=ask(d1,d2,r)-ask(d1,d2,l-1);

	ans+=mod;

	ans%=mod;

	return ans;

}

int f[SIZE][M][2];

int main()

{

	n=read(),m=read();

	for(RI i=1;i<=n;i++)

		a[i].x=read(),a[i].y=read();

	sort(a+1,a+1+n,cmp);

	add(0,a[1].y,0,1);

	add(0,a[1].y,1,1);

	for(RI i=2;i<=n;i++)

	{

		f[i][0][0]=f[i][0][1]=1;

		for(RI j=1;j<=m;j++)

			f[i][j][0]=(query(j,0,1,a[i].y-1)+query(j-1,1,1,a[i].y-1))%mod,

			f[i][j][1]=(query(j,1,a[i].y+1,MAXV)+query(j-1,0,a[i].y+1,MAXV))%mod;

		for(RI j=0;j<=m;j++)

			add(j,a[i].y,0,f[i][j][0]),add(j,a[i].y,1,f[i][j][1]);

	}

	printf("%d\n",(ask(m,0,MAXV)+ask(m,1,MAXV))%mod);

	return 0;

}

\[thanks \ for \ watching
\]

巴特西

题解 bzoj3688【折线统计】

Code 部分

最新文章

热门文章