[COGS 2897] [THUPC 2017] 맨 날 사격 좋아해.

COGS 전송 문
제목 설명
C 군 은 이 게임 에서 총알 로 널 빤 지 를 깨 뜨 릴 수 있 는 '매일 사랑 사격' 이라는 게임 을 사랑 하 게 되 었 다.그림 에서 보 듯 이 이 게임 은 x 축 과 평행 하 는 널빤지 가 있다.현재 약간의 총알 이 있 는데, 순서대로 Y 축 방향 을 따라 이 널빤지 들 을 향 해 쏜 다.제 i i 조각 나무판 자 는 S i Si. Si 총알 이 뚫 리 면 부서 지고 사라 집 니 다.한 개의 총알 이 그 궤적 의 모든 널 빤 지 를 관통 할 수 있다. 특히 한 개의 총알 이 널빤지 의 가장자리 에 닿 으 면 널 빤 지 를 관통 하 는 것 으로 간주 된다.
작은 C 는 이제 게임 에서 n n 개의 널빤지 위 치 를 알 게 되 었 고 m m 의 총알 시작 위 치 를 알 게 되 었 다.지금 당신 에 게 모든 총알 이 발사 되면 몇 개의 널빤지 가 뚫 릴 것 이 냐 고 물 었 습 니 다.
입력 형식
첫 번 째 줄 의 두 정수 n n n 과 m m 는 널빤지 의 수량 과 총알 의 수량 을 나타 낸다.그 중 1 ≤ n, m ≤ 200, 000 1 \ \ le n, m \ \ le 200, 000 1 ≤ n, m ≤ 200, 000.
다음 n n 줄, 줄 당 3, 3 개의 정수 x 1, x 2, S x1,x_2. S x1, x2, S 는 모든 널빤지 의 왼쪽 끝 점 x x x 좌표, 오른쪽 끝 점 x x x x 좌표, 그리고 몇 번 을 관통 하면 깨 진 다 는 것 을 나타 낸다.그 중 보증 1 ≤ x 1 ≤ x 2 ≤ 200, 000 1 \ \ le x1 \le x_2 \ \ le 200, 000 1 ≤ x1 ≤ x2 ≤ 200, 000 및 1 ≤ S ≤ 200, 000 1 \ \ \ le S \ \ le 200, 000 1 ≤ S ≤ 200, 000.
다음 m m 줄 은 줄 마다 정수 x x x x 로 모든 총알 의 x x x 좌 표를 나타 낸다.총알 은 발사 순서에 따라 내 놓 았 다.그 중 보증 1 ≤ x ≤ 200, 000 1 \ \ le x \ le 200, 000 1 ≤ x ≤ 200, 000.
출력 형식
m m 줄, 줄 마다 정수.총알 한 발 이 쏜 후 몇 개의 널빤지 가 깨 졌 는 지 나타 낸다.
샘플 입력

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

샘플 출력

1
2

데이터 범위 및 알림
30% 의 데이터 에 대하 여 n, m ≤ 1000 n, m \ le 1000 n, m ≤ 1000, 나머지 는 제목 에 따라 설명 한다.
100% 의 데이터 에 대하 여 n, m ≤ 200, 000 n, m \ le 200, 000 n, m ≤ 200, 000, 나머지 는 제목 에 따라 설명 한다.
문제 풀이 분석
전체 2 점, 2 점, 각 널 빤 지 는 몇 번 째 사격 후 깨 지고, B I T BIT BIT 는 구간 내 총탄 수 를 집계 한다.
하지만 일부 널 빤 지 는 끝까지 깨 지지 않 았 을 수도 있 으 니.....................................................................
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#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
", ans[i]);
}