当前位置:   article > 正文

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

天天爱天天怕
COGS传送门

题目描述

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

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

img

输入格式

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

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

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

输出格式

m m 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 ≤ 1000 n,m \le 1000 n,m1000,其余按题目描述所示

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

解题分析

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

不过注意有些木板可能到最后都没有被打烂… 所以当二分到 l = r l=r 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/800727
推荐阅读
相关标签
  

闽ICP备14008679号