P3332 K大数查询 题解

Solution

整体二分板子题

vector 太好写了111

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 50010;
int n, m, ans[N];
struct Modify {
	int tim, l, r, c;
};
struct Query {
	int tim, l, r, id;
	ll k;
};
vector<Modify> Ms;
vector<Query> Qs;

#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)

ll sum[N << 2], add[N << 2];
int len[N << 2];
void up(int u) {
	sum[u] = sum[lc] + sum[rc];
}
void Add(int u, ll v) {
	add[u] += v, sum[u] += 1ll * len[u] * v;
}
void down(int u) {
	if (add[u]) Add(lc, add[u]), Add(rc, add[u]), add[u] = 0;
}
void Build(int u, int l, int r) {
	len[u] = r - l + 1;
	if (l == r) return;
	Build(lc, l, mid), Build(rc, mid + 1, r);
}
void Upd(int u, int l, int r, int x, int y, ll v) {
	if (y < l || r < x || x > y) return;
	if (x <= l && r <= y) return Add(u, v);
	down(u), Upd(lc, l, mid, x, y, v), Upd(rc, mid + 1, r, x, y, v), up(u);
}
ll Qry(int u, int l, int r, int x, int y) {
	if (y < l || r < x || x > y) return 0ll;
	if (x <= l && r <= y) return sum[u];
	return down(u), Qry(lc, l, mid, x, y) + Qry(rc, mid + 1, r, x, y);
}

#undef lc
#undef rc
#undef mid

void Solve(int l, int r, vector<Modify> &M, vector<Query> &Q) {
	if (l == r) {
		for (auto p : Q)
			ans[p.id] = l - n - 1;
		return;
	}
	int mid = (l + r) >> 1, x = mid - n - 1;
	vector<Modify> mL, mR;
	vector<Query> qL, qR;
	int Msize = M.size(), Qsize = Q.size();
	for (int i = 0, j = 0; j < Qsize || i < Msize; ) {
		if (i < Msize && (j >= Qsize || M[i].tim < Q[j].tim)) {
			if (M[i].c <= x) {
				mL.push_back(M[i]);
			} else {
				Upd(1, 1, n, M[i].l, M[i].r, 1);
				mR.push_back(M[i]);
			}
			++i;
		} else {
			ll cnt = Qry(1, 1, n, Q[j].l, Q[j].r);
			if (Q[j].k > cnt) {
				Q[j].k -= cnt;
				qL.push_back(Q[j]);
			} else {
				qR.push_back(Q[j]);
			}
			++j;
		}
	}
	for (auto p : M)
		if (p.c > x) Upd(1, 1, n, p.l, p.r, -1);
	Solve(l, mid, mL, qL), Solve(mid + 1, r, mR, qR);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	int tot = 0;
	rep(i, 1, m) {
		int op, a, b, c;
		cin >> op >> a >> b >> c;
		if (op == 1) Ms.push_back((Modify){i, a, b, c});
		if (op == 2) Qs.push_back((Query){i, a, b, ++tot, c});
	}
	Build(1, 1, n);
	Solve(1, 2 * n + 1, Ms, Qs);
	rep(i, 1, tot) cout << ans[i] << '\n';
	return 0;
}