[Ceoi2011]Match

题目大意：初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。有m次操作，每次包含两个数ri，xi代表来了xi个ri号脚的人。xi为负，则代表走了这么多人。对于每次操作，输出溜冰鞋是否足够。

数据范围：n m k d ( 1≤n≤200,000 ， 1≤m≤500,000 ， 1≤k≤10^9 ， 0≤d≤n ) ri xi （ 1≤i≤m， 1≤ri≤n-d ， |xi|≤10^9 ）

题解：

这个题是个好题呀。

首先我们考虑，只有最后一次让输出是否合法怎么做。

显然就是每个人拿离自己近的鞋子，按照这个规则贪心显然是最优的。

进而我们考虑满分做法。

我想这个题的时候出现了一个误区就是一定要一步一步弄出答案，其实我们可以将整个式子量化。

比如说$i$号鞋有$w_i$人，如果不合法就当且仅当存在一个$a$和$b$满足：$\sum\limits_{i = a} ^ b w_i > (b - a + 1 + d) * k$。

这式子等价于$\sum\limits_{i = a} ^ b (w_i - k) > d * k$。

就只需要维护最大连续子段和即可。

那如果要求的是最小的不合法鞋子编号呢？

只需要在线段树上贪心就好了呀。

代码：

#include <bits/stdc++.h>

#define ls p << 1

#define rs p << 1 | 1

#define N 200010 

using namespace std;

typedef long long ll;

struct Node {

	ll al, lx, rx, mx;

	Node() {al = lx = rx = mx = 0;}

	friend Node operator + (const Node &a, const Node &b) {

		Node re;

		re.mx = max(a.rx + b.lx, max(a.mx, b.mx));

		re.lx = max(a.lx, a.al + b.lx);

		re.rx = max(b.rx, b.al + a.rx);

		re.al = a.al + b.al;

		return re;

	}

}a[N << 2];

inline void newnode(int p, ll val) {

	a[p].al = val;

	a[p].mx = a[p].lx = a[p].rx = val;

}

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

inline void pushup(int p) {

	a[p] = a[ls] + a[rs];

}

void update(int x, ll val, int l, int r, int p) {

	if (l == r) {

		newnode(p, val+a[p].mx);

		return;

	}

	int mid = (l + r) >> 1;

	if (x <= mid)

		update(x, val, l, mid, ls);

	else

		update(x, val, mid + 1, r, rs);

	pushup(p);

}

Node query(int x, int y, int l, int r, int p) {

	if (x <= l && r <= y) {

		return a[p];

	}

	int mid = (l + r) >> 1;

	Node re;

	if (x <= mid)

		re = re + query(x, y, l, mid, ls);

	if (mid < x)

		re = re + query(x, y, mid + 1, r, rs);

	return re;

}

int main() {

	int n = rd(), m = rd();

	ll k = rd(), d = rd();

	for (int i = 1; i <= n; i ++ ) {

		update(i, -k, 1, n, 1);

	}

	// cout << query(1, n, 1, n, 1).mx << endl ;

	for (int i = 1; i <= m; i ++ ) {

		ll r = rd();

		int x = rd();

		// for (int j = 1; j <= n; j ++ )

			// printf("%lld ",query(j, j, 1, n, 1));

		// puts("");

		update(r, x, 1, n, 1);

		if (query(1, n, 1, n, 1).mx > d * k)

			puts("NIE");

		else

			puts("TAK");

	}

	return 0;

}

小结：有些题目可以通过把约束变成式子，也是一种非常好的解题思路。

巴特西

[bzoj1135][Ceoi2011]Match_线段树

[Ceoi2011]Match

最新文章

热门文章