[THUPC2017] 天天爱射击

题目描述

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

小 C 现在知道了游戏中 \(n\) 块木板位置，以及知道了 \(m\) 个子弹射击位置。现在问你每个子弹射出去以后，有多少木板会碎掉？

输入格式

从标准输入读入数据。

第一行两个整数 \(n\) 和 \(m\)，表示木板数量和子弹数量。其中 \(1\le n,m\le 2\times 10^5\)。

接下来 \(n\) 行，每行三个整数 \(x_1,x_2,s\)，表示每块木板的左端点 \(x\) 坐标、右端点 \(x\) 坐标，以及贯穿多少次会碎掉。其中保证 \(1\le x_1\le x_2\le2\times 10^5,1\le s\le 2\times 10^5\)。

接下来 \(m\) 行，每行一个整数 ，表示每个子弹的 \(x\) 坐标。子弹按照发射顺序给出。其中保证 \(1\le x\le2\times 10^5\)。

输出格式

输出到标准输出。

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

样例 #1

样例输入 #1

3 2
1 3 1
2 4 2
3 4 1
2
3

样例输出 #1

1
2

提示

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。

\(\text{upd}2021.7.6\)：感谢 @jiangbowen 提供的一组 hack 数据，不计分，但若不通过 hack 数据则不算通过此题。

第一眼很没有思路。
这怎么做？

其实还好，但是我即使知道这是整体二分的题目，第一眼还是不知道怎么做。
其实是很裸的整体二分。
考虑进行n次二分答案怎么做。
对每一个木板进行二分答案。二分它在第几次射击中碎裂。

那就知道了，确实很裸

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char c=getchar();int a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int tr[200001],n,m,Maxr,ans[200001],pl[200001],Get[200001];
inline int lowbit(int x)
{
	return x&(-x);
}
inline void add(int i,int x)
{
	while(i<=Maxr)
	{
		tr[i]+=x;
		i+=lowbit(i);
	}
}
inline int ask(int i)
{
	int ans=0;
	while(i>0)
	{
		ans+=tr[i];
		i-=lowbit(i);
	}
	return ans;
}
struct board
{
	int l,r,k;
	int id;
}q[200001],ql[200001],qr[200001];
void solve(int st,int ed,int l,int r)
{
//	cout<<st<<' '<<ed<<' '<<l<<' '<<r<<endl;
	if(l>r)return;
	if(st==ed)
	{
		for(int i=l;i<=r;i++)
		{
			ans[q[i].id]=st;
		}
		return;
	}
	int mid=st+ed>>1;
	for(int i=st;i<=mid;i++)
	{
		add(pl[i],1);
	}
	int tl=0,tr=0;
	for(int i=l;i<=r;i++)
	{
		int tmp=ask(q[i].r)-ask(q[i].l-1);
		if(tmp>=q[i].k)
		{
			ql[++tl]=q[i];
		}
		else
		{
			qr[++tr]=q[i];
			qr[tr].k-=tmp;
		}
	}
	for(int i=st;i<=mid;i++)
		add(pl[i],-1);
	for(int i=l;i<=l+tl-1;i++)
		q[i]=ql[i-l+1];
	for(int i=l+tl;i<=r;i++)
		q[i]=qr[i-l-tl+1];
	solve(st,mid,l,l+tl-1);
	solve(mid+1,ed,l+tl,r);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		q[i].l=read();q[i].r=read();q[i].k=read();
		q[i].id=i;
		Maxr=max(Maxr,q[i].r);
	}
	for(int i=1;i<=m;i++)
	{
		pl[i]=read();
	}
	solve(1,m+1,1,n);
	for(int i=1;i<=n;i++)
	{
//		cout<<ans[i]<<' ';
		Get[ans[i]]++;
	}
//	cout<<endl;
	for(int i=1;i<=m;i++)
	{
		cout<<Get[i]<<endl;
	}
	return 0;
}
/*
5 3
1 4 2
2 3 1
3 4 1
1 5 3
3 5 2
1
3
2
*/

一个细节，就是整体二分的值域要开大一些。

像上面，如果我solve里面的m+1是m的话，就会错，这个其实是在考虑如果有板子没被打碎的情况。
如果不开到m+1，它就会默认在m停下，事实上不可以。

还好我这次试了一个例子，不然要wa一次了。