[玄关] 二分+树状数组 WA 求调
查看原帖
[玄关] 二分+树状数组 WA 求调
950357
Wayming2025楼主2024/8/12 09:50

rt

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define space ' '
int n, m, bul[200005], ans[200005], tree[200005];
struct Wood {
	int l, r, t;
} wood[200005], lq[200005], rq[200005];
inline void insert(int x, int y) {
	for (; x <= n; x += x & -x)
		tree[x] += y;
}
inline int query(int x) {
	int sum = 0;
	for (; x; x -= x & -x)
		sum += tree[x];
	return sum;
}
inline void solve(int l, int r, int b, int e) {
	if (b > e)
		return ;
	if (l == r) {
		for (int i = b; i <= e; i++)
			if (wood[i].t == 1 and wood[i].l <= bul[i] and wood[i].r >= bul[i])
				ans[l]++;
		return ;
	}
	int mid = (l + r) >> 1, l_1 = 0, r_1 = 0;
	for (int i = l; i <= mid; i++)
		insert(bul[i], 1);
	for (int i = b; i <= e; i++) {
		if ((query(wood[i].r) - query(wood[i].l - 1)) >= wood[i].t)
			lq[++l_1] = wood[i];
		else 
			rq[++r_1] = {
			wood[i].l, wood[i].r, wood[i].t - (query(wood[i].r) - query(wood[i].l - 1))
		};
	}
	for (int i = l; i <= mid; i++)
		insert(bul[i], -1);
	for (int i = 1; i <= l_1; i++)
		wood[b + i - 1] = lq[i];
	for (int i = 1; i <= r_1; i++)
		wood[b + l_1 + i - 1] = rq[i];
	solve(l, mid, b, b + l_1 - 1);
	solve(mid + 1, r, b + l_1, e);
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> wood[i].l >> wood[i].r >> wood[i].t;
	}
	for (int i = 1; i <= m; i++)
		cin >> bul[i];
	solve(1, m, 1, n);
	for (int i = 1; i <= m; i++)
		cout << ans[i] << endl;
	return 0;
}
2024/8/12 09:50
加载中...