[COGS 2897] [THUPC 2017] 天天爱射击_天天爱天天怕

COGS传送门

题目描述

小C爱上了一款名字叫做《天天爱射击》的游戏，在这款游戏中可以用子弹将木板打碎。如图所示，这个游戏有一些平行于x轴的木板。现在有一些子弹，按顺序沿着y轴方向向这些木板射去。第$i$块木板被$S_i$个子弹击穿以后，就会碎掉消失。一个子弹可以贯穿其轨迹上的全部木板，特别的，如果一个子弹触碰到木板的边缘，也视为贯穿木板。

小C现在知道了游戏中$n$块木板位置，以及知道了$m$个子弹起始位置。现在问你每个子弹射出去以后，有多少木板会被击穿？

输入格式

第一行两个整数$n$和$m$，表示木板数量和子弹数量。其中$1\le n,m\le 200,000$。

接下来$n$行，每行$3$个整数$x_1,x_2,S$，表示每块木板的左端点$x$坐标、右端点$x$坐标，以及贯穿多少次会碎掉。其中保证$1\le x_1\le x_2\le 200,000$ 且$1\le S\le 200,000$。

接下来$m$行，每行一个整数$x$，表示每个子弹的$x$坐标。子弹按照发射顺序给出。其中保证$1\le x\le 200,000$。

输出格式

$m$ 行，每行一个整数。表示每颗子弹射出去后，有多少木板碎掉。

样例输入

3 2
1 3 1
2 4 2
3 4 1
2
3
1
2
3
4
5
6

样例输出

1
2
1
2

数据范围及提示

对于30%的数据，$n,m\le 1000$，其余按题目描述所示

对于100%的数据，$n,m\le 200,000$，其余按题目描述所示

解题分析

整体二分， 二分每块木板会在第几次射击后破碎， $BIT$统计区间内子弹数量

不过注意有些木板可能到最后都没有被打烂… 所以当二分到$l=r$的时候加个判断。

代码如下：

#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 200500
#define lbt(i) ((i) & (-(i)))
template <class T>
IN void in(T &x)
{
	x = 0; R char c = gc;
	for (; !isdigit(c); c = gc);
	for (;  isdigit(c); c = gc)
	x = (x << 1) + (x << 3) + c - 48;
}
int n, m;
struct opt {int lef, rig, k;} dat[MX], buf1[MX], buf2[MX];
int tree[MX], ans[MX], hit[MX];
IN void add(R int pos, R int del) {for (; pos <= n; pos += lbt(pos)) tree[pos] += del;}
IN int query(R int pos)
{
	int ret = 0;
	for (; pos; pos -= lbt(pos)) ret += tree[pos];
	return ret;
}
void solve(R int lef, R int rig, R int lb, R int rb)
{
	int cnt1 = 0, cnt2 = 0, res;
	if (lef > rig || lb > rb) return;
	if (lb == rb)
	{
		for (R int i = lef; i <= rig; ++i)
		if (dat[i].k == (dat[i].lef <= hit[lb] && dat[i].rig >= hit[lb])) ++ans[lb];
		return;
	}
	int mid = lb + rb >> 1;
	for (R int i = lb; i <= mid; ++i) add(hit[i], 1);
	for (R int i = lef; i <= rig; ++i)
	{
		res = query(dat[i].rig) - query(dat[i].lef - 1);
		if (res >= dat[i].k) buf1[++cnt1] = dat[i];
		else buf2[++cnt2] = dat[i], buf2[cnt2].k -= res;
	}
	for (R int i = lb; i <= mid; ++i) add(hit[i], -1);
	for (R int i = 1; i <= cnt1; ++i) dat[lef + i - 1] = buf1[i];
	for (R int i = 1; i <= cnt2; ++i) dat[lef + cnt1 + i - 1] = buf2[i];
	solve(lef, lef + cnt1 - 1, lb, mid), solve(lef + cnt1, rig, mid + 1, rb);
}
int main(void)
{
	freopen("shooting.in", "r", stdin), freopen("shooting.out", "w", stdout);
	in(n), in(m);
	for (R int i = 1; i <= n; ++i) in(dat[i].lef), in(dat[i].rig), in(dat[i].k);
	for (R int i = 1; i <= m; ++i) in(hit[i]);
	solve(1, n, 1, m);
	for (R int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62