题解

每块木板只关心自己被第几颗子弹击穿：对区间 $[l_i,r_i]$ 内的子弹编号按发射顺序排序，取第 $S_i$ 个，就能知道哪一颗子弹使得木板碎掉。于是问题就转化为：给定 $m$ 个位置（子弹射击的 $x$），多次询问某个区间内的第 $k$ 小编号是多少。

按照 $x$ 坐标从小到大枚举所有位置，把该位置上的所有子弹（发射时间已知）依次插入一棵可持久化权值线段树。第 $j$ 个版本就是“所有 $x\le j$ 的子弹对应的编号集合”。这样，区间 $[l,r]$ 上的所有子弹就是 rt[qzh[r]] 与 rt[qzh[l-1]] 两个版本求差得到的树，直接在树上二分即可找到第 $S_i$ 个编号。再把对应子弹的答案加一，就知道每颗子弹打碎了多少块木板。

时空复杂度均为 $\mathcal{O}((n+m)\log m)$。

#include<bits/stdc++.h>
using namespace std;
int ans[200005],qryl[200005],qryr[200005],x[200005],rt[200005],tot,qzh[200005],p[200005];
struct stu{
	int l,r,x;
}tr[20000005];
vector<int>v[200005];
void add(int &id,int l,int r,int x)
{
	tr[++tot]=tr[id];
	id=tot;
	tr[id].x++;
	if(l==r) return ;
	int mid=l+r>>1;
	if(x<=mid) add(tr[id].l,l,mid,x);
	else add(tr[id].r,mid+1,r,x);
}
int fnd(int id1,int id2,int l,int r,int w)
{
	if(tr[id1].x-tr[id2].x<w) return 0;
	if(l==r) return l;
	int mid=l+r>>1,ans=0;
	if(w<=tr[tr[id1].l].x-tr[tr[id2].l].x) return fnd(tr[id1].l,tr[id2].l,l,mid,w);
	else return fnd(tr[id1].r,tr[id2].r,mid+1,r,w-(tr[tr[id1].l].x-tr[tr[id2].l].x));
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,minn=2e5,maxx=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>qryl[i]>>qryr[i]>>x[i];
		minn=min(minn,qryl[i]);
		maxx=max(maxx,qryr[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int w;
		cin>>w;
		v[w].push_back(i);
		qzh[w]++;
	}
	for(int i=1;i<=200000;i++) qzh[i]+=qzh[i-1];
	int cnt=0;
	for(int i=1;i<=200000;i++)
	{
		for(auto j:v[i])
		{
			cnt++;
			rt[cnt]=rt[cnt-1];
			add(rt[cnt],1,200000,j);
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans[fnd(rt[qzh[qryr[i]]],rt[qzh[qryl[i]-1]],1,200000,x[i])]++;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}