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

数据范围及提示

对于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]);
}