K大数查询 wu-kan

题目链接

看到巨佬们在群里膜 CDQ,于是来学习 CDQ 分治…

要避免树状数组重复初始化,每次操作完之后要将树状数组恢复。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9;
struct Fenwick
{
	struct BaseFenwick
	{
		vector<ll> v;
		BaseFenwick(int n) : v(n) {}
		void add(int x, ll w)
		{
			for (; x < v.size(); x += x & -x)
				v[x] += w;
		}
		ll ask(int x)
		{
			ll ans = 0;
			for (; x; x -= x & -x)
				ans += v[x];
			return ans;
		}
	};
	pair<BaseFenwick, BaseFenwick> p;
	Fenwick(int n) : p(n, n) {}
	void add(int x, ll w) { p.first.add(x, w), p.second.add(x, x * w); }
	void add(int l, int r, ll w) { add(l, w), add(r + 1, -w); }
	ll ask(int x) { return (x + 1) * p.first.ask(x) - p.second.ask(x); }
	ll ask(int l, int r) { return ask(r) - ask(l - 1); }
} t(N);
struct Query
{
	int o, a, b, ans;
	ll c;
} q[N];
void ask(int l, int r, const vector<int> &id)
{
	if (l == r)
	{
		for (int i = 0; i < id.size(); ++i)
			if (q[id[i]].o != 1)
				q[id[i]].ans = l;
		return;
	}
	ll m = l + r >> 1;
	vector<int> t1, t2;
	for (int i = 0; i < id.size(); ++i)
	{
		if (q[id[i]].o == 1)
		{
			if (q[id[i]].c <= m)
				t1.push_back(id[i]);
			else
				t2.push_back(id[i]), t.add(q[id[i]].a, q[id[i]].b, 1);
		}
		else
		{
			ll sum = t.ask(q[id[i]].a, q[id[i]].b);
			if (q[id[i]].c > sum)
				t1.push_back(id[i]), q[id[i]].c -= sum;
			else
				t2.push_back(id[i]);
		}
	}
	for (int i = 0; i < t2.size(); ++i)
		if (q[t2[i]].o == 1)
			t.add(q[t2[i]].a, q[t2[i]].b, -1);
	ask(l, m, t1), ask(m + 1, r, t2);
}
int main()
{
	int n, m;
	vector<int> id;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i)
	{
		id.push_back(i);
		scanf("%d%d%d%lld", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
	}
	ask(1, n, id);
	for (int i = 0; i < m; ++i)
		if (q[i].o != 1)
			printf("%d\n", q[i].ans);
}

动态开点线段树自然也是行的,不过慢了六七倍(2400ms:15744ms)…

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9, NPOS = -1;
struct SegmentTree
{
	struct Val
	{
		int l, r;
		ll sum;
		void upd(ll add) { sum += add * (r - l + 1); }
	};
	struct Node
	{
		Val v;
		int lc, rc;
		ll add;
	};
	vector<Node> v;
	SegmentTree(int l, int r) { build(l, r); }
	void build(int l, int r) { v.push_back({{l, r, 0}, NPOS, NPOS, 0}); }
	Val up(const Val &lc, const Val &rc) { return {lc.l, rc.r, lc.sum + rc.sum}; }
	void down(int rt)
	{
		int m = v[rt].v.l + v[rt].v.r >> 1;
		if (v[rt].lc == NPOS)
			v[rt].lc = v.size(), build(v[rt].v.l, m);
		if (v[rt].rc == NPOS)
			v[rt].rc = v.size(), build(m + 1, v[rt].v.r);
		upd(v[v[rt].lc].v.l, v[v[rt].lc].v.r, v[rt].add, v[rt].lc);
		upd(v[v[rt].rc].v.l, v[v[rt].rc].v.r, v[rt].add, v[rt].rc);
		v[rt].add = 0;
	}
	void upd(int l, int r, ll add, int rt = 0)
	{
		if (l <= v[rt].v.l && v[rt].v.r <= r)
			return v[rt].add += add, v[rt].v.upd(add);
		down(rt);
		if (r <= v[v[rt].lc].v.r)
			upd(l, r, add, v[rt].lc);
		else if (l >= v[v[rt].rc].v.l)
			upd(l, r, add, v[rt].rc);
		else
			upd(l, v[v[rt].lc].v.r, add, v[rt].lc), upd(v[v[rt].rc].v.l, r, add, v[rt].rc);
		v[rt].v = up(v[v[rt].lc].v, v[v[rt].rc].v);
	}
	Val ask(int l, int r, int rt = 0)
	{
		if (l <= v[rt].v.l && v[rt].v.r <= r)
			return v[rt].v;
		down(rt);
		if (r <= v[v[rt].lc].v.r)
			return ask(l, r, v[rt].lc);
		if (l >= v[v[rt].rc].v.l)
			return ask(l, r, v[rt].rc);
		return up(ask(l, v[v[rt].lc].v.r, v[rt].lc), ask(v[v[rt].rc].v.l, r, v[rt].rc));
	}
};
struct Query
{
	int o, a, b, ans;
	ll c;
} q[N];
int n, m;
void ask(int l, int r, const vector<int> &id)
{
	if (l == r)
	{
		for (int i = 0; i < id.size(); ++i)
			if (q[id[i]].o != 1)
				q[id[i]].ans = l;
		return;
	}
	ll m = l + r >> 1;
	SegmentTree t(1, n);
	vector<int> t1, t2;
	for (int i = 0; i < id.size(); ++i)
	{
		if (q[id[i]].o == 1)
		{
			if (q[id[i]].c <= m)
				t1.push_back(id[i]);
			else
				t2.push_back(id[i]), t.upd(q[id[i]].a, q[id[i]].b, 1);
		}
		else
		{
			ll sum = t.ask(q[id[i]].a, q[id[i]].b).sum;
			if (q[id[i]].c > sum)
				t1.push_back(id[i]), q[id[i]].c -= sum;
			else
				t2.push_back(id[i]);
		}
	}
	ask(l, m, t1), ask(m + 1, r, t2);
}
int main()
{
	vector<int> id;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i)
	{
		id.push_back(i);
		scanf("%d%d%d%lld", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
	}
	ask(1, n, id);
	for (int i = 0; i < m; ++i)
		if (q[i].o != 1)
			printf("%d\n", q[i].ans);
}

在线的做法是树套树。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9, M = 2e7 + 9;
struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
} rk;
struct Query
{
	int o, a, b, c;
} q[N];
struct Node
{
	int lc, rc, add;
	ll sum;
} t[M];
int n, m, tot, root[N << 2];
void upd(int u, int v, int &rt, int l, int r, ll add);
void down(int rt, int l, int r)
{
	if (!t[rt].add)
		return;
	int m = l + r >> 1;
	upd(l, m, t[rt].lc, l, m, t[rt].add);
	upd(m + 1, r, t[rt].rc, m + 1, r, t[rt].add);
	t[rt].add = 0;
}
void upd(int u, int v, int &rt, int l, int r, ll add)
{
	if (!rt)
		rt = ++tot;
	if (u == l && v == r)
	{
		t[rt].add += add, t[rt].sum += (r - l + 1) * add;
		return;
	}
	down(rt, l, r);
	int m = l + r >> 1;
	if (v <= m)
		upd(u, v, t[rt].lc, l, m, add);
	else if (u > m)
		upd(u, v, t[rt].rc, m + 1, r, add);
	else
		upd(u, m, t[rt].lc, l, m, add), upd(m + 1, v, t[rt].rc, m + 1, r, add);
	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;
}
ll ask(int u, int v, int rt, int l, int r)
{
	if (!rt)
		return 0;
	if (u == l && v == r)
		return t[rt].sum;
	down(rt, l, r);
	int m = l + r >> 1;
	if (v <= m)
		return ask(u, v, t[rt].lc, l, m);
	if (u > m)
		return ask(u, v, t[rt].rc, m + 1, r);
	return ask(u, m, t[rt].lc, l, m) + ask(m + 1, v, t[rt].rc, m + 1, r);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i)
	{
		scanf("%d%d%d%d", &q[i].o, &q[i].a, &q[i].b, &q[i].c);
		if (q[i].o == 1)
			rk.push_back(q[i].c);
	}
	rk.init();
	for (int i = 0; i < m; ++i)
	{
		if (q[i].o == 1)
			for (int c = rk.size() - rk.ask(q[i].c), k = 1, l = 1, r = rk.size();;)
			{
				int m = l + r >> 1;
				upd(q[i].a, q[i].b, root[k], 1, n, 1);
				if (l == r)
					break;
				if (c <= m)
					r = m, k <<= 1;
				else
					l = m + 1, k = k << 1 | 1;
			}
		else
		{
			int k = 1, l = 1, r = rk.size();
			while (l < r)
			{
				ll m = l + r >> 1, sum = ask(q[i].a, q[i].b, root[k << 1], 1, n);
				if (sum >= q[i].c)
					r = m, k <<= 1;
				else
					l = m + 1,
					k = k << 1 | 1, q[i].c -= sum;
			}
			printf("%d\n", rk[rk.size() - l]);
		}
	}
}