记录编号	600820	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	天天爱射击	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	4.893 s
提交时间	2025-05-19 15:30:26	内存使用	36.28 MiB

#include <bits/stdc++.h>
using namespace std;
#define N 200000
int n, m, l, r, x, mx, now, cnt, lst, ans[200010], t[200010];
struct node{
	int l, r, val;
}a[200010];
struct ask{
	int x, y;
	bool operator < (const ask &A) const{
		return x < A.x;
	}
}q[200010];
struct segment{
	int l, r, s;
}d[5000010];
void modify(int &p, int lst, int l, int r, int x){
	if (!p || p == lst) d[p=++cnt]=d[lst];
	d[p].s ++;
	if (l == r) return ;
	int mid = l + r >> 1;
	if (x <= mid) modify(d[p].l, d[lst].l, l, mid, x);
	else modify(d[p].r, d[lst].r, mid+1, r, x);
}
int query(int p, int lst, int l, int r, int x){
	if (x > d[p].s - d[lst].s) return 0;
	if (l == r) return l;
	int mid = l + r >> 1, dif = d[d[p].l].s - d[d[lst].l].s;
	if (dif >= x) return query(d[p].l, d[lst].l, l, mid, x);
	else return query(d[p].r, d[lst].r, mid+1, r, x-dif);
}
int main(){
		freopen("shooting.in","r",stdin);
			freopen("shooting.out","w",stdout);
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=n; i++){
		scanf ("%d%d%d", &a[i].l, &a[i].r, &a[i].val);
		mx = max(mx, a[i].r);
	}
	for (int i=1; i<=m; i++){
		scanf ("%d", &q[i].x);
		q[i].y = i;
	}
	sort (q+1, q+m+1);
	for (int i=1; i<=m; i++){
		for (int j=lst+1; j<q[i].x; j++){
			t[j] = t[j-1];
		}
		modify(t[q[i].x], t[q[i].x-1], 1, N, q[i].y);
		lst = q[i].x;
	}
	for (int i=lst+1; i<=mx; i++) t[i] = t[i-1];
	for (int i=1; i<=n; i++){
		now = query(t[a[i].r], t[a[i].l-1], 1, N, a[i].val);
		ans[now] ++;
	}
	for (int i=1; i<=m; i++){
		printf ("%d\n", ans[i]);
	}
	return 0;
}