[bzoj 3688] 折线统计

二维平面上有n个点, 不存在两个点有相同的横/纵坐标. S是点集的一个子集, 把S中的点按横坐标依次连线, 求增减性变化(k-1)次的S的数目模10^5+7. (n≤5*10^4, 0<k≤10) 点按横坐标排序, 从左往右扫描.

设 为以 结尾, 共 段, 最后一段增减性为 的集合的数目. 同理.

这是一个前/后缀和. 外层枚举 , 把同一个 扔进一棵线段树/树状数组即可.

#define x first
#define y second

const int MOD = 1e5 + 7, N = 1e5 + 1, K = 11;

pair<int, int> P[N/2];
int g[K][2][N], s[K][2];

void add(int* x, int i, int v)
{
	while (i < N) (x[i] += v) %= MOD, i += i&-i;
}

void add(int j, int k, int i, int v)
{
	(s[j][k] += v) %= MOD;
	add(g[j][k], i, v);
}

int sum(int* x, int i)
{
	int v = 0;
	while (i) (v += x[i]) %= MOD, i -= i&-i;
	return v;
}

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	rep (i, 0, n) scanf("%d%d", &P[i].x, &P[i].y);
	sort(P, P+n);
	rep (i, 0, n)
	{
		add(0, 0, P[i].y, 1);
		add(0, 1, P[i].y, 1);
		rep (j, 1, k+1)
		{
			int t = sum(g[j][1], P[i].y-1) + sum(g[j-1][0], P[i].y-1);
			add(j, 1, P[i].y, t);
			t = s[j][0] - sum(g[j][0], P[i].y) + s[j-1][1] - sum(g[j-1][1], P[i].y);
			add(j, 0, P[i].y, t);
		}
	}
	int ans = ((s[k][0] + s[k][1]) % MOD + MOD) % MOD;
	printf("%d\n", ans);
	return 0;
}