题目链接

很久之前就做过这个题，但是当时只会简单套模板。打算重新学一下可持久化数据结构。

现在我对可持久化数据结构的理解是每次修改时保留原信息，只在修改的地方增加新的修改节点。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int NPOS = -1;
struct HJTree
{
	struct Val
	{
		int l, r;
		ll sum;
		void upd(ll add) { sum += (r - l + 1) * add; }
	};
	struct Node
	{
		Val v;
		int lc, rc;
	};
	vector<Node> v;
	vector<int> root;
	HJTree(int n) : root{0} { v.reserve(3e6), build(1, n); }
	void build(int l, int r)
	{
		v.push_back({{l, r, 0}, NPOS, NPOS});
		if (l >= r)
			return;
		int m = l + r >> 1, rt = v.size() - 1;
		v[rt].lc = v.size(), build(l, m);
		v[rt].rc = v.size(), build(m + 1, r);
	}
	Val up(const Val &lc, const Val &rc) { return {lc.l, rc.r, lc.sum + rc.sum}; }
	void upd(int pos, int add, int rt)
	{
		if (pos <= v[rt].v.l && v[rt].v.r <= pos)
			return v[rt].v.upd(add);
		if (pos > v[v[rt].lc].v.r)
			v.push_back(v[v[rt].rc]), upd(pos, add, v[rt].rc = v.size() - 1);
		else
			v.push_back(v[v[rt].lc]), upd(pos, add, v[rt].lc = v.size() - 1);
		v[rt].v = up(v[v[rt].lc].v, v[v[rt].rc].v);
	}
	void push_back(int pos) { v.push_back(v[root.back()]), root.push_back(v.size() - 1), upd(pos, 1, root.back()); }
	int h_index(int lx, int rx)
	{
		lx = root[lx - 1], rx = root[rx];
		for (int now = 0; v[lx].v.l < v[lx].v.r;)
		{
			if (v[v[rx].rc].v.sum - v[v[lx].rc].v.sum + now < v[v[lx].rc].v.l)
				now += v[v[rx].rc].v.sum - v[v[lx].rc].v.sum, lx = v[lx].lc, rx = v[rx].lc;
			else
				lx = v[lx].rc, rx = v[rx].rc;
		}
		return v[lx].v.l;
	}
};
int main()
{
	for (int n, q; ~scanf("%d%d", &n, &q);)
	{
		HJTree t(n);
		for (int i = 0, a; i < n; ++i)
			scanf("%d", &a), t.push_back(a);
		for (int l, r; q--; printf("%d\n", t.h_index(l, r)))
			scanf("%d%d", &l, &r);
	}
}

一年前敲得还是二分…

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct Node
{
	int ch[2], sum;
} v[N << 5];
struct HJTree
{
	int siz, root[N];
	void add(int p, int &x, int y, int l, int r)
	{
		v[x = siz++].sum = v[y].sum + 1;
		if (l == r)
			return;
		int m = (l + r) / 2;
		if (p <= m)
		{
			add(p, v[x].ch[0], v[y].ch[0], l, m);
			v[x].ch[1] = v[y].ch[1];
		}
		else
		{
			v[x].ch[0] = v[y].ch[0];
			add(p, v[x].ch[1], v[y].ch[1], m + 1, r);
		}
	}
	int ask(int x, int y, int k, int l, int r)
	{
		if (l == r)
			return v[y].sum - v[x].sum;
		int m = (l + r) / 2;
		if (k <= m)
			return v[v[y].ch[1]].sum - v[v[x].ch[1]].sum +
				   ask(v[x].ch[0], v[y].ch[0], k, l, m);
		return ask(v[x].ch[1], v[y].ch[1], k, m + 1, r);
	}
} t;
int main()
{
	for (int n, q; ~scanf("%d%d", &n, &q);)
	{
		for (int i = t.siz = 1, a; i <= n; ++i)
			scanf("%d", &a), t.add(a, t.root[i], t.root[i - 1], 1, n);
		for (int i = 1, x, y, l, r, m; i <= q; ++i, printf("%d\n", r))
			for (scanf("%d%d", &x, &y), l = 2, r = n; l <= r;)
			{
				m = l + (r - l) / 2;
				if (t.ask(t.root[x - 1], t.root[y], m, 1, n) >= m)
					l = m + 1;
				else
					r = m - 1;
			}
	}
}