526互联

可持久化线段树小记

发布时间 2023-11-29 19:04:56作者: __honey

可持久化线段树小记
首先你需要完成这两个模板：P3919 【模板】可持久化线段树 1（可持久化数组） P3834 【模板】可持久化线段树 2

T1 P1383 高级打字机

题意：

\(n\) 个询问，\(3\) 种操作：
1.T x：在文章末尾打下一个小写字母 \(x\)。
2.U x：撤销最后的 \(x\) 次修改操作。
3.Q x：询问当前文章中第 \(x\) 个字母并输出，\(Q\) 操作不算修改操作。
文章开始为空串。
\(1 \leq n \leq 10^5\)。

分析：

可以直接在序列上建立可持久化线段树，每一次修改对应一个版本，线段树下标表示某个小写字母，查询操作就是两个版本查询区间第 \(x\) 小。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5;

class hjtree
{
	public:
		struct smt
		{
			int l,r,s,ch;
		}tree[N<<5];
		int tot;
		
		void pushup(int x)
		{
			tree[x].s = tree[tree[x].l].s+tree[tree[x].r].s;
		}
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s;
			if(l == r)
			{
				tree[x].s = 1;
				tree[x].ch = p;
				return ;
			}
			int mid = (l+r)/2;
			if(tree[tree[x].l].s < mid-l+1) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
			pushup(x);
		}
		
		int query(int x,int l,int r,int k)
		{
			if(l == r) return tree[x].ch;
			int mid = (l+r)/2;
			if(tree[tree[x].l].s >= k) return query(tree[x].l,l,mid,k);
			else return query(tree[x].r,mid+1,r,k-tree[tree[x].l].s);
		}
}ss;

int n,rt[N],cnt;

int main()
{
	read(n);
	for(int i = 1;i <= n;i++)
	{
		char opt[10]; scanf("%s",opt);
		if(*opt == 'T')
		{
			scanf("%s",opt);
			++cnt,ss.modify(rt[cnt],rt[cnt-1],1,n,*opt-'a');
		}
		else
		{
			int x; read(x);
			if(*opt == 'U') ++cnt,rt[cnt] = rt[cnt-x-1];
			else printf("%c\n",ss.query(rt[cnt],1,n,x)+'a');
		}
	}
	return (0-0); // QwQ
}

T2 P2464 [SDOI2008] 郁闷的小 J

题意：

有 \(n\) 本书，每本书有一个编码 \(a_i\)，\(m\) 次询问，两种类型：
1.C A P：将 \(a_A\) 修改成 \(P\)。
2.Q A B K：查询区间 \(A\) 到 \(B\) 中编码为 \(K\) 的书有多少本。
\(1 \leq n,m \leq 10^5,0 \leq a_i,P,K \leq 2^{31}-1\)。

分析：

首先把所有的编码离散化，可以在编码上建立可持久化线段树，线段树下标表示序列区间，然后只需要修改对应编码版本，在某个版本上区间查询即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5;

struct Q
{
	int opt,l,r,x;
}e[N];

int n,m,a[N],b[N*2],rt[N*2];

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N<<6];
		int tot;
		
		void pushup(int x)
		{
			tree[x].s = tree[tree[x].l].s+tree[tree[x].r].s;
		}
		
		void modify(int &x,int l,int r,int p,int v)
		{
			if(!x) x = ++tot;
			if(l == r)
			{
				tree[x].s += v;
				return ;
			}
			int mid = (l+r)/2; 
			if(p <= mid) modify(tree[x].l,l,mid,p,v);
			else modify(tree[x].r,mid+1,r,p,v);
			pushup(x);
		}
		
		int query(int x,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[x].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[x].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[x].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(a[i]),b[i] = a[i];
	for(int i = 1;i <= m;i++)
	{
		char opt[10]; scanf("%s",opt);
		if(*opt == 'C')
		{
			int x,p; read(x); read(p);
			e[i] = {0,x,p,0};
			b[i+n] = p;
		}
		else
		{
			int l,r,x; read(l); read(r); read(x);
			e[i] = {1,l,r,x};
			b[i+n] = x;
		}
	}
	sort(b+1,b+1+n+m);
	int len = unique(b+1,b+1+n+m)-b-1;
	for(int i = 1;i <= n;i++)
	{
		a[i] = lower_bound(b+1,b+1+len,a[i])-b;
		ss.modify(rt[a[i]],1,n,i,1);
	}
	for(int i = 1;i <= m;i++)
	{
		if(e[i].opt == 0)
		{
			int p = e[i].l;
			ss.modify(rt[a[p]],1,n,p,-1);
			a[p] = lower_bound(b+1,b+1+len,e[i].r)-b;
			ss.modify(rt[a[p]],1,n,p,1);
		}
		else
		{
			int x = lower_bound(b+1,b+1+len,e[i].x)-b;
			printf("%d\n",ss.query(rt[x],1,n,e[i].l,e[i].r));
		}
	}
	return (0-0); // QwQ
}

T3 P7252 [JSOI2011] 棒棒糖

题意：

给一个长度为 \(n\) 的数列 \(a\)，\(m\) 次询问，每次询问一个区间内有没有一个数出现次数严格超过一半，如果存在输出这个数，否则输出 \(0\)。
\(1 \leq n,m,a_i \leq 5 \times 10^4\)。

分析：

如果一个数在区间中出现次数严格超过区间长度的一半，那这个区间大部分都是这个数，可以随机撒若干次点，每次查询这个数出现次数是否严格超过区间一半，这个操作只需要在数字上建立可持久化线段树，线段树下标表示序列区间，查询某个数在区间出现次数即可。
假设一个区间存在出现次数严格大于区间长度的数，那么撒一次点不能找到这个数的概率为 \(\frac{1}{2}\)，撒 \(x\) 次不能找到的概率是 \((\frac{1}{2})^x\)，无法找到的概率非常低，本题此方法可以通过。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 5e5+5;

int n,m,a[N],rt[N];

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*20];
		int tot;
		
		inline void pushup(int x)
		{
			tree[x].s = tree[tree[x].l].s+tree[tree[x].r].s;
		}
		
		inline void modify(int &x,int l,int r,int p)
		{
			if(!x) x = ++tot;
			if(l == r)
			{
				tree[x].s++;
				return ;
			}
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,l,mid,p);
			else modify(tree[x].r,mid+1,r,p);
			pushup(x);
		}
		
		inline int query(int x,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[x].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[x].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[x].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int main()
{
	srand(time(0));
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[a[i]],1,n,i);
	while(m--)
	{
		int l,r; read(l); read(r);
		int ans = 0;
		for(int i = 1;i <= 20;i++)
		{
			int t = rand()%(r-l+1)+l;
			int ret = ss.query(rt[a[t]],1,n,l,r);
			if(ret > (r-l+1)/2) ans = a[t];
		}
		printf("%d\n",ans);
	}
	return (0-0); // QwQ
}

T4 P3567 [POI2014] KUR-Couriers

题意：

给一个长度为 \(n\) 的数列 \(a\)，\(m\) 次询问，每次询问一个区间内有没有一个数出现次数严格超过一半，如果存在输出这个数，否则输出 \(0\)。
\(1 \leq n,m,a_i \leq 5 \times 10^5\)。

分析：

上述做法在本题无法通过，考虑在序列上建立可持久化线段树，线段树下标表示数字，每次查询就是递归查询是否存在一个叶子结点上对应的数字满足条件。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 5e5+5;

int n,m,a[N],rt[N];

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*20];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		
		int query(int u,int v,int l,int r,int len)
		{
			if(l == r) return l;
			int mid = (l+r)/2;
			if(tree[tree[u].l].s-tree[tree[v].l].s > len/2) return query(tree[u].l,tree[v].l,l,mid,len);
			if(tree[tree[u].r].s-tree[tree[v].r].s > len/2) return query(tree[u].r,tree[v].r,mid+1,r,len);
			return 0;
		}
}ss;

int main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[i],rt[i-1],1,n,a[i]);
	while(m--)
	{
		int l,r; read(l); read(r);
		printf("%d\n",ss.query(rt[r],rt[l-1],1,n,r-l+1));
	}
	return (0-0); // QwQ
}

T5 P2468 [SDOI2010] 粟粟的书架

题意：

给定一个 $ R \times C$ 的矩阵 \(a\)，\(M\) 次询问。
每次询问形如 x1 y1 x2 y2 h，表示询问在 \((x1,y1)\) 到 \((x2,y2)\) 形成的子矩形中，至少要选多少个数，使得这几个数的和不小于 \(h\)，如果无法做到，输出 Poor QLW。
有 \(50 \%\) 的数据 \(R,C \leq 200,M \leq 2 \times 10^5\)。
另外 \(50 \%\) 的数据 \(R=1,C \leq 5 \times 10^5,M \leq 2 \times 10^4\)。
\(1 \leq a_{i,j},1 \leq h \leq 2 \times 10^9\)。

分析：

对于前 \(50 \%\) 的数据，可以考虑前缀和，\(f(i,j,k),g(i,j,k)\) 分别表示覆盖 \((1,1)\) 到 \((i,j)\) 的矩阵，矩阵中数不小于 \(x\) 的数字之和 和数量他们的数量。
然后就可以二分这个最小需要的数字个数。
时间复杂度：\(O(1000RC+m \log (1000))\)
对于后 \(50 \%\) 的数据，矩阵退化成一个序列，可以在序列上建立可持久化线段树，线段树下标表示序列中的数字。
可以二分选数的个数 \(k\)，查询区间前 \(k\) 大的数字之和。
时间复杂度：\(O(C \log C+M \log ^2 C)\)。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define x1 ___x1
#define y1 ___y1
#define x2 ___x2
#define y2 ___y2
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 205,M = 5e5+5;

int n,m,q;

namespace sub1
{
	int a[M],rt[M];
	class segment
	{
		public:
			struct smt
			{
				int l,r,s,sum;
			}tree[M*20];
			int tot;
			
			void modify(int &x,int pre,int l,int r,int p)
			{
				x = ++tot;
				tree[x].l = tree[pre].l;
				tree[x].r = tree[pre].r;
				tree[x].s = tree[pre].s+1;
				tree[x].sum = tree[pre].sum+p;
				if(l == r) return ;
				int mid = (l+r)/2;
				if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
				else modify(tree[x].r,tree[pre].r,mid+1,r,p);
			}
			
			int query(int u,int v,int l,int r,int k)
			{
				if(l == r) return (k+l-1)/l;
				int t = tree[tree[u].r].sum-tree[tree[v].r].sum;
				int mid = (l+r)/2;
				if(t >= k) return query(tree[u].r,tree[v].r,mid+1,r,k);
				else return query(tree[u].l,tree[v].l,l,mid,k-t)+tree[tree[u].r].s-tree[tree[v].r].s;
			}
	}ss;
	void work()
	{
		n = m,m = 1000;
		for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[i],rt[i-1],1,m,a[i]);
		while(q--)
		{
			int x,l,y,r,h; read(x); read(l); read(y); read(r); read(h);
			if(ss.tree[rt[r]].sum-ss.tree[rt[l-1]].sum < h) {puts("Poor QLW"); continue;}
			printf("%d\n",ss.query(rt[r],rt[l-1],1,m,h));
		}
	}
};

namespace sub2
{
	int a[N][N],f[N][N][1005],g[N][N][1005];
	int query(int x1,int y1,int x2,int y2,int k,int op)
	{
		if(op) return f[x2][y2][k]-f[x1-1][y2][k]-f[x2][y1-1][k]+f[x1-1][y1-1][k];
		else return g[x2][y2][k]-g[x1-1][y2][k]-g[x2][y1-1][k]+g[x1-1][y1-1][k];
	}
	void work()
	{
		for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) read(a[i][j]);
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++)
				for(int k = 1000;k;k--)
				{
					if(a[i][j] >= k) f[i][j][k] = a[i][j],g[i][j][k] = 1;
					f[i][j][k] += f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k];
					g[i][j][k] += g[i-1][j][k]+g[i][j-1][k]-g[i-1][j-1][k];
				}
		while(q--)
		{
			int x1,y1,x2,y2,h; read(x1); read(y1); read(x2); read(y2); read(h);
			if(query(x1,y1,x2,y2,1,1) < h) {puts("Poor QLW"); continue;} 
			int l = 1,r = 1000;
			while(l < r)
			{
				int mid = (l+r+1)/2;
				if(query(x1,y1,x2,y2,mid,1) >= h) l = mid;
				else r = mid-1;
			}
			printf("%d\n",query(x1,y1,x2,y2,l,0)-(query(x1,y1,x2,y2,l,1)-h)/l);
				
		}
	}
};

int main()
{
	read(n); read(m); read(q);
	if(n == 1) sub1::work();
	else sub2::work();
	return (0-0); // QwQ
}

T6 https://www.luogu.com.cn/problem/P2633

题意：

给定一个 \(n\) 个结点的树，每个结点有点权 \(a\)，\(m\) 次询问，每次查询两个点间简单路径上经过结点的第 \(k\) 小点权，强制在线。
\(1 \leq n,m \leq 10^5,1 \leq a_i \leq 2^{31}-1\)。

分析：

可以先求出 \(dfs\) 序，然后在 \(dfs\) 序上求区间第 \(k\) 小，利用差分的思想，区间第 \(k\) 小是序列上的差分，树上第 \(k\) 小是树上差分，查询记录 \(u,v,lca,fa[lca]\) 四个版本即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5;

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*20];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		
		int query(int a,int b,int c,int d,int l,int r,int k)
		{
			if(l == r) return l;
			int t = tree[tree[a].l].s+tree[tree[b].l].s-tree[tree[c].l].s-tree[tree[d].l].s;
			int mid = (l+r)/2;
			if(t >= k) return query(tree[a].l,tree[b].l,tree[c].l,tree[d].l,l,mid,k);
			else return query(tree[a].r,tree[b].r,tree[c].r,tree[d].r,mid+1,r,k-t);
		}
}ss;

int n,m,q,a[N],st[N*2][19],tot,pos[N],lg[N*2],b[N],faz[N],dep[N],rt[N];
vector <int> g[N];

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	faz[u] = fa;
	pos[u] = ++tot;
	st[tot][0] = u;
	ss.modify(rt[u],rt[fa],1,m,a[u]);
	for(auto x:g[u])
	{
		if(x == fa) continue;
		dfs(x,u);
		st[++tot][0] = u;
	}
}

void init()
{
	for(int i = 2;i <= tot;i++) lg[i] = lg[i/2]+1;
	for(int j = 1;(1<<j) <= tot;j++)
		for(int i = 1;i+(1<<j)-1 <= tot;i++)
			if(dep[st[i][j-1]] < dep[st[i+(1<<(j-1))][j-1]]) st[i][j] = st[i][j-1];
			else st[i][j] = st[i+(1<<(j-1))][j-1];
}

int lca(int u,int v)
{
	int l = pos[u],r = pos[v];
	if(l > r) swap(l,r);
	int k = lg[r-l+1];
	if(dep[st[l][k]] < dep[st[r-(1<<k)+1][k]]) return st[l][k];
	else return st[r-(1<<k)+1][k];
}

int main()
{
	read(n); read(q);
	for(int i = 1;i <= n;i++) read(a[i]),b[i] = a[i];
	sort(b+1,b+1+n);
	m = unique(b+1,b+1+n)-b-1;
	for(int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+1+m,a[i])-b;
	for(int i = 1;i < n;i++)
	{
		int u,v; read(u); read(v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0),init();
	int la = 0;
	while(q--)
	{
		int u,v,k; read(u); read(v); read(k);
		u ^= la;
		int p = lca(u,v);
		la = b[ss.query(rt[u],rt[v],rt[p],rt[faz[p]],1,m,k)];
		printf("%d\n",la); 
	}
	return (0-0); // QwQ
}

T7 P3302 [SDOI2013] 森林

题意：

有一个 \(n\) 个结点,\(m\) 条边的森林，每个节点都有一个权值 \(a_i\)，有 \(T\) 次询问，两种操作：
1.Q x y k：查询 \(x,y\) 结点之间简单路径上经过结点的第 \(k\) 小点权。
2.L x y：在 \(x,y\) 之间连一条边，满足连完边后还是一个森林。
\(1 \leq n,m,T \leq 8 \times 10^4,M < N,a_i \leq 10^9\)，强制在线。

分析：

加边操作，可以类似并查集的按秩合并，每次重构 \(siz\) 小的部分，询问操作就是普通的树上查询区间第 \(k\) 小，套用 \(T6\) 代码即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 8e4+5;

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*300];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		
		int query(int a,int b,int c,int d,int l,int r,int k)
		{
			if(l == r) return l;
			int t = tree[tree[a].l].s+tree[tree[b].l].s-tree[tree[c].l].s-tree[tree[d].l].s;
			int mid = (l+r)/2;
			if(t >= k) return query(tree[a].l,tree[b].l,tree[c].l,tree[d].l,l,mid,k);
			else return query(tree[a].r,tree[b].r,tree[c].r,tree[d].r,mid+1,r,k-t);
		}
}ss;

int tid,n,m,q,a[N],b[N],f[N][18],rt[N],siz[N],fa[N],dep[N];
vector <int> g[N];

int find(int x){return fa[x] = (x == fa[x]?x:find(fa[x]));}
bool merge(int x,int y)
{
	int r1 = find(x),r2 = find(y);
	if(r1 == r2) return 0;
	fa[r1] = r2;
	siz[r2] += siz[r1];
	return 1;
}

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	f[u][0] = fa;
	ss.modify(rt[u],rt[fa],1,m,a[u]);
	for(int j = 1;j <= 17;j++) f[u][j] = f[f[u][j-1]][j-1];
	for(auto x:g[u])
	{
		if(x == fa) continue;
		dfs(x,u);
	}
}

int lca(int u,int v)
{
	if(dep[v] > dep[u]) swap(u,v);
	for(int i = 17;i >= 0;i--) if(dep[f[u][i]] >= dep[v]) u = f[u][i];
	if(u == v) return u;
	for(int i = 17;i >= 0;i--) if(f[u][i] != f[v][i]) u = f[u][i],v = f[v][i];
	return f[u][0];
}

int main()
{
	read(tid); read(n); read(m); read(q);
	for(int i = 1;i <= n;i++) read(a[i]);
	for(int i = 1;i <= n;i++) fa[i] = i,siz[i] = 1;
	for(int i = 1;i <= m;i++)
	{
		int u,v; read(u); read(v);
		g[u].push_back(v);
		g[v].push_back(u);
		merge(u,v);
	}
	for(int i = 1;i <= n;i++) b[i] = a[i];
	sort(b+1,b+1+n);
	m = unique(b+1,b+1+n)-b-1;
	for(int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+1+m,a[i])-b;
	for(int i = 1;i <= n;i++) if(find(i) == i) dfs(i,0);
	int la = 0;
	while(q--)
	{
		char opt[10]; scanf("%s",opt);
		int u,v; read(u); read(v);
		u ^= la,v ^= la;
		if(*opt == 'Q')
		{
			int k; read(k);
			k ^= la;
			int p = lca(u,v);
			la = b[ss.query(rt[u],rt[v],rt[p],rt[f[p][0]],1,m,k)];
			printf("%d\n",la);
		}
		else
		{
			g[u].push_back(v);
			g[v].push_back(u);
			int r1 = find(u),r2 = find(v);
			if(siz[r1] > siz[r2]) swap(u,v);
			merge(u,v),dfs(u,v);
		}
	}
	return (0-0); // QwQ
}

T8 P2839 [国家集训队] middle

题意：

给定一个长度为 \(n\) 的序列 \(s\)，有 \(Q\) 次询问：
a b c d：\(s\) 的左端点在 \([a,b]\)之间，右端点在 \([c,d]\) 之间的子区间中，最大的中位数（这里的中位数是指将长度为 \(n\) 的序列排序后，下标为 \(b_{n/2}\) 的数。
\(1 \leq n \leq 20000,1 \leq Q \leq 25000,1 \leq a_i \leq 10,a < b < c < d\)，强制在线。

分析：

考虑二分得到一个 \(x\)，将小于 \(x\) 的数设为 \(-1\)，其他设为 \(1\)，那么 \(x\) 能成为序列的中位数当且仅当 \([a,b]\) 的右最大子段和，\([b+1,c-1]\) 的区间和，\([c,d]\) 的左最大子段和，这三项之和不小于 \(0\)(这样就有至少一半的数小于等于\(x\))。
可以在数值上建立可持久化线段树，线段树下标表示区间，上面三种操作都是线段树的经典操作，维护 \(lmax,rmax,sum\) 即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 2e4+5;

PII e[N];

class segment
{
	public:
		struct smt
		{
			int l,r,sum,lmx,rmx;
		}tree[N*30];
		int tot;
		
		void pushup(smt &x,smt &l,smt &r)
		{
			x.sum = l.sum+r.sum;
			x.lmx = max(l.lmx,l.sum+r.lmx);
			x.rmx = max(r.rmx,r.sum+l.rmx);
		}
		
		void build(int &x,int l,int r)
		{
			x = ++tot;
			if(l == r)
			{
				tree[x].sum = tree[x].lmx = tree[x].rmx = 1;
				return ;
			}
			int mid = (l+r)/2;
			build(tree[x].l,l,mid),build(tree[x].r,mid+1,r);
			pushup(tree[x],tree[tree[x].l],tree[tree[x].r]);
		}
		
		void modify(int &x,int pre,int l,int r,int p,int v)
		{
			x = ++tot;
			tree[x] = tree[pre];
			if(l == r)
			{
				tree[x].sum = tree[x].lmx = tree[x].rmx = v;
				return ;
			}
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p,v);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p,v);
			pushup(tree[x],tree[tree[x].l],tree[tree[x].r]);
		}
		
		int qsum(int x,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[x].sum;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += qsum(tree[x].l,l,mid,ql,qr);
			if(qr > mid) ret += qsum(tree[x].r,mid+1,r,ql,qr);
			return ret;
		}
		
		smt qmx(int x,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[x];
			int mid = (l+r)/2;
			if(ql > mid) return qmx(tree[x].r,mid+1,r,ql,qr);
			else if(qr <= mid) return qmx(tree[x].l,l,mid,ql,qr);
			else
			{
				smt s1 = qmx(tree[x].l,l,mid,ql,qr);
				smt s2 = qmx(tree[x].r,mid+1,r,ql,qr);
				smt ans = tree[x];
				pushup(ans,s1,s2);
				return ans;
			}
		}
}ss;

int n,q,Q[5],rt[N];

bool check(int x)
{
	auto r1 = ss.qmx(rt[x],1,n,Q[1],Q[2]);
	auto r2 = ss.qmx(rt[x],1,n,Q[3],Q[4]);
	int s1 = r1.rmx,s2 = r2.lmx;
	int s3 = 0;
	if(Q[2]+1 <= Q[3]-1) s3 = ss.qsum(rt[x],1,n,Q[2]+1,Q[3]-1);
	return (s1+s2+s3) >= 0;
}

int main()
{
	read(n);
	for(int i = 1;i <= n;i++) read(e[i].fi),e[i].se = i;
	sort(e+1,e+1+n);
	ss.build(rt[0],1,n);
	for(int i = 1;i <= n;i++) ss.modify(rt[i],rt[i-1],1,n,e[i].se,-1);
	read(q);
	int la = 0;
	while(q--)
	{
		for(int i = 1;i <= 4;i++) read(Q[i]);
		for(int i = 1;i <= 4;i++) Q[i] = (Q[i]+la)%n+1;
		sort(Q+1,Q+1+4);
		int l = 0,r = n;
		while(l < r)
		{
			int mid = (l+r+1)/2;
			if(check(mid)) l = mid;
			else r = mid-1;
		}
		la = e[l+1].fi;
		printf("%d\n",la);
	}
	return (0-0); // QwQ
}

T9 U218735 绘梦Ⅲ

题意：

有一棵 \(n\) 个结点，\(n-1\) 条边的树，任意两个结点间接或直接联通，每条边有一个权值，有 \(m\) 次询问：
a b k：结点 \(a\) 到结点 \(b\) 的简单路径上有多少条边的权值小于等于 \(k\)。
\(1 \leq n,m \leq 10^5\)，结点权值在 \(int\) 范围内。

分析：

我们先考虑在序列上怎么做，先把权值离散化，那么可以在序列上建立可持久化线段树，线段树下标表示权值，那么一次询问就是询问区间小于等于 \(k\) 的个数，这个直接在两个版本上差分即可。
当询问在树上，可以直接重链剖分，将树上问题转化为序列，每次跳 \(top\) 即可。
时间复杂度：\(O(n \log^2 n)\)。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5;

struct slpf
{
	int dfn,siz,dep,rk,son,top,fa;
}ee[N];

int rt[N],m;

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*40];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		
		int query(int u,int v,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[v].s-tree[u].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[u].l,tree[v].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[u].r,tree[v].r,mid+1,r,ql,qr);
			return ret;
		}
		
		int ask(int x,int y,int k)
		{
			int fx = ee[x].top,fy = ee[y].top;
			int ret = 0;
			while(fx != fy)
			{
				if(ee[fx].dep >= ee[fy].dep)
				{
					ret += query(rt[ee[fx].dfn-1],rt[ee[x].dfn],1,m,1,k);
					x = ee[fx].fa,fx = ee[x].top;
				}
				else
				{
					ret += query(rt[ee[fy].dfn-1],rt[ee[y].dfn],1,m,1,k);
					y = ee[fy].fa,fy = ee[y].top;
				}
			}
			if(ee[x].dfn >= ee[y].dfn) swap(x,y);
			ret += query(rt[ee[x].dfn],rt[ee[y].dfn],1,m,1,k);
			return ret;
		}
}ss;

struct ques
{
	int x,y,k;
}Q[N];

int n,q,tim,c[N],b[N*2];
vector <PII> g[N];

void dfs1(int u,int fa)
{
	ee[u].dep = ee[fa].dep+1;
	ee[u].siz = 1;
	ee[u].fa = fa;
	for(auto x:g[u])
	{
		int j = x.fi;
		if(j == fa) continue;
		dfs1(j,u);
		c[j] = x.se;
		ee[u].siz += ee[j].siz;
		if(!ee[u].son || ee[j].siz > ee[ee[u].son].siz) ee[u].son = j;
	}
}

void dfs2(int u,int t)
{
	ee[u].dfn = ++tim;
	ee[u].top = t;
	ee[tim].rk = u;
	if(!ee[u].son) return ;
	dfs2(ee[u].son,t);
	for(auto x:g[u])
	{
		int j = x.fi;
		if(j == ee[u].fa || j == ee[u].son) continue;
		dfs2(j,j);
	}
}

int main()
{
	read(n); read(q);
	for(int i = 1;i < n;i++)
	{
		int u,v,w; read(u); read(v); read(w);
		g[u].push_back({v,w});
		g[v].push_back({u,w});
		b[++m] = w;
	}
	for(int i = 1;i <= q;i++)
	{
		int l,r,k; read(l); read(r); read(k);
		Q[i] = {l,r,k};
		b[++m] = k;
	}
	sort(b+1,b+1+m);
	m = unique(b+1,b+1+m)-b-1;
	dfs1(1,0),dfs2(1,1);
	for(int i = 1;i <= n;i++)
	{
		int p = lower_bound(b+1,b+1+m,c[ee[i].rk])-b;
		ss.modify(rt[i],rt[i-1],1,m,p);
	}
	for(int i = 1;i <= q;i++)
	{
		int x = Q[i].x,y = Q[i].y,k = Q[i].k;
		int p = lower_bound(b+1,b+1+m,k)-b;
		printf("%d\n",ss.ask(x,y,p));
	}
	return (0-0); // QwQ
}

T10 P3168 [CQOI2015] 任务查询系统

题意：

有 \(n\) 项任务，每项任务用 \((s_i,e_i,p_i)\)描述，表示第 \(i\) 项任务从 \(s_i\) 开始，在 \(e_i\) 结束（包含 \(s_i,e_i\)），优先级为 \(p_i\)。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。
有 \(m\) 次询问，每次询问，你需要回答在时间为 \(x_i\) 时刻，所有在工作中的任务优先级前 \(k_i\) 的任务的优先级之和。
\(1 \leq n,m \leq 10^5,1 \leq s_i \leq e_i \leq m,1 \leq p_i \leq 10^7\)，\(x_i\) 为 \(m\) 的一个排列，强制在线。

分析：

如果 \(k\) 固定，且没有强制在线，可以从小到大枚举时刻，然后用一个堆记录前 \(k\) 小的值以及他们的和。
对于本题，区间修改，单调查询，考虑差分，可以在时刻序列上建立可持久化线段树，线段树下标表示优先级（要离散化），然后只需要查询某个版本的区间前 \(k\) 小值之和即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5;

class segment
{
	public:
		struct smt
		{
			int l,r,cnt; LL sum;
		}tree[N*40];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p,int v,int vv)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].cnt = tree[pre].cnt+v;
			tree[x].sum = tree[pre].sum+vv;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p,v,vv);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p,v,vv);
		}
		
		LL query(int x,int l,int r,int k)
		{
			if(l == r) return tree[x].sum/max(1,tree[x].cnt)*k;
			int t = tree[tree[x].l].cnt;
			int mid = (l+r)/2;
			if(t >= k) return query(tree[x].l,l,mid,k);
			else return query(tree[x].r,mid+1,r,k-t)+tree[tree[x].l].sum;
		}
}ss;

struct pos
{
	int l,r,x;
}e[N];

int n,m,q,b[N],rt[N];
vector <PII> g[N];

int main()
{
	read(n); read(q);
	for(int i = 1;i <= n;i++)
	{
		int l,r,x; read(l); read(r); read(x);
		e[i] = {l,r,x};
		g[l].push_back({i,1});
		g[r+1].push_back({i,-1});
		b[i] = x;
	}
	sort(b+1,b+1+n);
	m = unique(b+1,b+1+n)-b-1;
	for(int i = 1;i <= n;i++) e[i].x = lower_bound(b+1,b+1+m,e[i].x)-b;
	for(int i = 1;i <= n;i++)
	{
		rt[i] = rt[i-1];
		for(auto x:g[i]) ss.modify(rt[i],rt[i],1,m,e[x.fi].x,x.se,x.se*b[e[x.fi].x]);
	}
	LL la = 1;
	while(q--)
	{
		int x,A,B,C; read(x); read(A); read(B); read(C);
		int k = (la*A+B)%C+1;
		la = ss.query(rt[x],1,m,k);
		printf("%lld\n",la);
	}
	return (0-0); // QwQ
}

T11 P3293 [SCOI2016] 美味

题意：

一道餐厅有 \(n\) 道菜，大家对第 \(i\) 道菜的评价为 \(a_i\)，有 \(m\) 为顾客，第 \(i\) 为顾客的期望值为 \(b_i\)，偏好值为 \(x_i\)。因此，第 \(i\) 位顾客认为第 \(j\) 道菜的美味度为 \(b_i \oplus (a_j+x_i)\)，其中 \(\oplus\) 表示异或运算。
对于每一位顾客，请求出，菜品在 \([l_i,r_i]\) 中的最大美味度。
\(1 \leq n \leq 2 \times 10^5,0 \leq a_i,b_i,x_i < 10^5,1 \leq l_i \leq r_i \leq n(1 \leq i \leq m),1 \leq m \leq 10^5\)。

分析：

看到异或值最大，大概可以联想到拆位逐位比较。
我们用 \(v\) 累计已经找完最优的 \(a_j+x_i\) 值，从高到低枚举 \(b_i\) 的每一位：
当 \(b_i\) 的第 \(k\) 位为 \(1\) 时，要知道是否有 \(a_j+x_i\) 满足这一位为 \(0\)，那么要判断 \([v-x_i,v+2^k-1-x_i]\) 中是否存在 \(a_j\)，如果不存在 \(v\) 的这一位就设为 \(1\)，否则为 \(0\)。
当 \(b_i\) 的第 \(k\) 位为 \(0\) 时，要知道是否有 \(a_j+x_i\) 满足这一位为 \(1\)，那么要判断 \([v+2^k-x_i,v+2^{k+1}-1-x_i]\) 中是否存在 \(a_j\)，如果不存在 \(v\) 的这一位就为 \(0\)，否则为 \(1\)。
然后 \(b_i \oplus v\) 就是答案。
要判断某个区间是否存在某个数，可以按照序列建可持久化线段树，线段树下标表示某个数，只需要在两个版本中区间查询即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 2e5+5,M = 1e5;

class segment
{
	public:
		struct smt
		{
			int l,r,s;
		}tree[N*20];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		
		int query(int u,int v,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[u].s-tree[v].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[u].l,tree[v].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[u].r,tree[v].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int n,m,a[N],rt[N];

int main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[i],rt[i-1],0,M,a[i]);
	while(m--)
	{
		int b,x,l,r; read(b); read(x); read(l); read(r);
		int ans = 0;
		for(int i = 17;i >= 0;i--)
		{
			if(b>>i&1)
			{
				int t = ss.query(rt[r],rt[l-1],0,M,max(0,ans)-x,min(M,ans+(1<<i)-1-x));
				if(!t) ans |= (1<<i);
			}
			else
			{
				int t = ss.query(rt[r],rt[l-1],0,M,max(0,ans+(1<<i)-x),min(M,ans+(1<<(i+1))-1-x));
				if(t) ans |= (1<<i);
			}
		}
		printf("%d\n",ans^b);
	}
	return (0-0); // QwQ
}

T12 P4602 [CTSC2018] 混合果汁

题意：

有 \(n\) 种果汁，第 \(i\) 个果汁的美味度为 \(d_i\)，每升价格为 \(p_i\)，在一瓶混合果汁中，\(i\) 号果汁最多添加 \(l_i\) 升。
有 \(m\) 个询问，每次询问形如 \((g_i,L_i)\)，表示他希望得到的混合果汁总价格不超过 \(g_i\)，总体积不小于 \(L_i\)，一瓶混合果汁的美味度等于参与混合的果汁的美味度的最小值，请最大化这个混合果汁的美味度，如果没有符合的果汁组合，请输出 -1。

分析：

最小值最大，显然暗示我们二分答案，可以二分最小的美味值 \(x\)，然后就是判断美味值大于等于 \(x\)，是否可以满足答案，可以将所有果汁按照美味度排序，然后在美味值上建立可持久化线段树，线段树下标表示价格，然后查询就是在某个版本上查询前 \(k\) 小价格的总和。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5,M = 1e5;

class segment
{
	public:
		struct smt
		{
			int l,r; LL s,sum;
		}tree[N*20];
		int tot;
		
		void modify(int &x,int pre,int l,int r,int p,int v,LL vv)
		{
			x = ++tot;
			tree[x].l = tree[pre].l;
			tree[x].r = tree[pre].r;
			tree[x].s = tree[pre].s+v;
			tree[x].sum = tree[pre].sum+vv;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p,v,vv);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p,v,vv); 
		}
		
		LL query(int x,int l,int r,LL k)
		{
			if(l == r) return k*l;
			LL t = tree[tree[x].l].s;
			int mid = (l+r)/2;
			if(t >= k) return query(tree[x].l,l,mid,k);
			else return query(tree[x].r,mid+1,r,k-t)+tree[tree[x].l].sum;
		}
}ss;

struct pos
{
	int d,p,l;
	friend bool operator < (pos a,pos b)
	{
		return a.d < b.d;
	}
}e[N];

int n,m,rt[N];

int main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(e[i].d),read(e[i].p),read(e[i].l);
	sort(e+1,e+1+n);
	for(int i = n;i;i--) ss.modify(rt[i],rt[i+1],1,M,e[i].p,e[i].l,1LL*e[i].p*e[i].l);
	while(m--)
	{
		LL G,L; read(G); read(L);
		int l = 1,r = n;
		while(l < r)
		{
			int mid = (l+r+1)/2;
			if(L <= ss.tree[rt[mid]].s && ss.query(rt[mid],1,M,L) <= G) l = mid;
			else r = mid-1;
		}
		if(L <= ss.tree[rt[l]].s && ss.query(rt[l],1,M,L) <= G) printf("%d\n",e[l].d);
		else puts("-1");
	}
	return (0-0); // QwQ
}

T13 P3963 [TJOI2013] 奖学金

题意：

有 \(n\) 个学生，成绩为 \(a_i\)，期望奖学金为 \(b_i\)。
要选出其中 \(m\) 人发奖学金，要求获得奖学金的同学成绩中位数尽量大，并且奖学金总额不超过 \(f\)，求出这个中位数的最大值。
\(3 \leq m \leq n \leq 10^5,0 \leq f,a_i \leq 2 \times 10^9,0 \leq b_i \leq 10^5\)。

分析：

令 \(k=\frac{m-1}{2}\)，那么对于一个 \(i\)，如果他是成绩的中位数，我们只需要求出成绩小于等于他的奖学金前 \(k\) 小和成绩大于等于他的奖学金前 \(k\) 小，判断他们的总和是否小于等于 \(f\) 即可。
可以按照成绩排序，分别令 \(f1(i),f2(i)\) 表示 \([1,i]\) 的学生中，奖学金前 \(k\) 小的总和，\([i,n]\) 的学生中，奖学金前 \(k\) 小的总和。
转移的话，考虑新加一个人，如果他需要的奖学金比前 \(i-1\) 个人的第 \(k\) 小的奖学金还少，那么选他更优，这样更新就行了。
因此我们需要一个能够查询区间第 \(k\) 的数据结构，很显然可持久化线段树即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 2e5+5,M = 1e5;

class segmnet
{
	public:
		struct smt{int l,r,s;}tree[N*20];
		int tot;
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l,tree[x].r = tree[pre].r,tree[x].s = tree[pre].s+1;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		int query(int u,int v,int l,int r,int k)
		{
			if(l == r) return l;
			int t = tree[tree[u].l].s-tree[tree[v].l].s,mid = (l+r)/2;
			if(t >= k) return query(tree[u].l,tree[v].l,l,mid,k);
			else return query(tree[u].r,tree[v].r,mid+1,r,k-t);
		}
}ss;

int n,m,rt[N];
LL f,f1[N],f2[N];
PII a[N];

int main()
{
	read(m); read(n); read(f); m = (m-1)/2;
	for(int i = 1;i <= n;i++) read(a[i].fi),read(a[i].se);
	sort(a+1,a+1+n);
	for(int i = 1;i <= n;i++) ss.modify(rt[i],rt[i-1],0,M,a[i].se);
	for(int i = 1;i <= m;i++) f1[i] = f1[i-1]+a[i].se;
	for(int i = n;i >= n-m+1;i--) f2[i] = f2[i+1]+a[i].se;
	for(int i = m+1;i <= n;i++) f1[i] = f1[i-1]+min(0,a[i].se-ss.query(rt[i-1],rt[0],0,M,m));
	for(int i = n-m;i;i--) f2[i] = f2[i+1]+min(0,a[i].se-ss.query(rt[n],rt[i],0,M,m));
	for(int i = n-m;i >= m+1;i--) if(a[i].se+f1[i-1]+f2[i+1] <= f) {printf("%d\n",a[i].fi);return (0-0);}
	puts("-1");
	return (0-0); // QwQ
}

T14 P3939 数颜色

题意：

给定长度为 \(n\) 的序列 \(c\)，\(m\) 次询问，两种操作：
1.1 l r c：查询区间 \([l,r]\) 中 \(c\) 的个数。
2.x：交换 \(c_x,c_{x+1}\)。
\(1 \leq n,m \leq 6 \times 10^5,1 \leq l < r \leq n,1 \leq x < n,c_i \leq 3 \times 10^5\)。

分析：

在颜色上建立线段树，线段树下标表示序列，查询操作是在某个版本上的区间查询，修改操作，只需要修改 \(x,x+1\) 的版本在下标为 \(x,x+1\) 上的值即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 3e5+5,M = 3e5;

class segment
{
	public:
		struct smt{int l,r,s;}tree[N*40];
		int tot;
		void pushup(int x){tree[x].s = tree[tree[x].l].s+tree[tree[x].r].s;}
		void modify(int &x,int l,int r,int p,int v)
		{
			if(!x) x = ++tot;
			if(l == r){tree[x].s += v;return ;}
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,l,mid,p,v);
			else modify(tree[x].r,mid+1,r,p,v);
			pushup(x);
		}
		int query(int x,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[x].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[x].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[x].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int n,m,a[N],rt[N];

int main()
{
	read(n); read(m);
	for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[a[i]],1,n,i,1);
	while(m--)
	{
		int opt; read(opt);
		if(opt == 1)
		{
			int l,r,c; read(l); read(r); read(c);
			printf("%d\n",ss.query(rt[c],1,n,l,r));
		}
		else
		{
			int x; read(x);
			ss.modify(rt[a[x]],1,n,x,-1),ss.modify(rt[a[x+1]],1,n,x,1);
			ss.modify(rt[a[x]],1,n,x+1,1),ss.modify(rt[a[x+1]],1,n,x+1,-1); 
			swap(a[x],a[x+1]);
		}
	}
	return (0-0); // QwQ
}

T15 P3899 [湖南集训] 更为厉害

题意：

转化一下就是说，给你一棵 \(n\) 个节点的树，根节点编号为 \(1\)，\(q\) 次询问，给定 \(a,k\)，求满足条件的三元组个数 \((a,b,c)\)，其中 \(b\) 与 \(a\) 的简单距离小于等于 \(k\)，且 \(a,b\) 都是 \(c\) 的祖先。
\(1 \leq n,q \leq 3 \times 10^5,1 \leq a,k \leq n\)。

分析：

要满足条件 \(b\) 有两种情况，是 \(a\) 的祖先或 \(a\) 的儿子。
当 \(b\) 是 \(a\) 的祖先时，答案是 \(min(k,dep_a-1) \times (siz_a-1)\)。
当 \(b\) 是 \(a\) 的儿子时，需要满足 \(dep_a \leq dep_b \leq dep_a+k\)。
对于 \(a\) 的每个能成为 \(b\) 的儿子，他的贡献是 \(siz_b-1\)。
那么我们就要求 \(\sum\limits_{b \in son_a,dep_a \leq dep_b \leq dep_a+k}(siz_b-1)\)。
可以在 \(dfs\) 序上建立可持久化线段树，线段树下标表示 \(dep\)，然后查询只需要在 \(a\) 的子树的版本里查询 \([dep_a+1,min(dep_a+k,n)]\) 的区间和即可。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 3e5+5;

class segment
{
	public:
		struct smt{int l,r; LL s;}tree[N<<5];
		int tot;
		void modify(int &x,int pre,int l,int r,int p,int v)
		{
			x = ++tot;
			tree[x].l = tree[pre].l,tree[x].r = tree[pre].r,tree[x].s = tree[pre].s+v;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p,v);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p,v);
		}
		LL query(int u,int v,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[u].s-tree[v].s;
			int mid = (l+r)/2; LL ret = 0;
			if(ql <= mid) ret += query(tree[u].l,tree[v].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[u].r,tree[v].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int n,q,dfn[N],tim,dep[N],siz[N],rt[N];
vector <int> g[N];

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	dfn[u] = ++tim;
	siz[u] = 1;
	for(auto x:g[u])
	{
		if(x == fa) continue;
		dfs(x,u);
		siz[u] += siz[x];
	}
}

void dfs1(int u,int fa)
{
	ss.modify(rt[dfn[u]],rt[dfn[u]-1],1,n,dep[u],siz[u]-1);
	for(auto x:g[u]) if(x != fa) dfs1(x,u);
}

int main()
{
	read(n); read(q);
	for(int i = 1;i < n;i++)
	{
		int u,v; read(u); read(v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0),dfs1(1,0);
	while(q--)
	{
		int u,k; read(u); read(k);
		LL ret = 1LL*min(k,dep[u]-1)*(siz[u]-1)+ss.query(rt[dfn[u]+siz[u]-1],rt[dfn[u]],1,n,dep[u]+1,min(dep[u]+k,n));
		printf("%lld\n",ret);
	}
	return (0-0); // QwQ
}

T16 P4587 [FJOI2016] 神秘数

题意：

给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问 \(l,r\)，询问由 \(a_l,a_{l+1},···,a_r\) 所组成的可重集合的神秘数。
一个可重集合 \(S\) 神秘数定义为最小的不能被 \(S\) 的子集的和表示的数。
\(1 \leq n,m \leq 10^5,\sum\limits a <= 10^9\)。

分析：

对于一个数 \(v\)，如果一个可重集合可以表示出 \([1,x]\)，如果 \(x+1 >= v\)，那么将 \(v\) 加入这个集合可以表示出 \([1,x+v]\)，否则这个集合的神秘数就是 \(x+1\)。
最暴力的做法就是将区间的数排序，然后依次加入判断，这样做是 \(O(nm \log n)\) 的。
转换一下，在序列上建立可持久化线段树，线段树下标表示集合中的数字。
只需要令 \(v\) 等于 \(1\)，然后不断在两个区间版本的线段树中查询 \([1,v]\) 中数字之和 \(s\) 是否大于等于 \(v\)，并更新 \(v\)，如果不可以得到就直接跳出即可。
有余每次更新，需要满足 \(s >= v\)，更新后 \(v \rightarrow s+1\)，而新的 \([1,v]\) 的数字之和，至少为 \(s\) 的两倍，因此这样做，跳的次数也不会很多，是 \(\log\) 的。
时间复杂度：\(O(m \log n(\sum\limits \log a_i))\)。

点击查看代码 
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<int,int> PII;
template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch;
	while((ch = getchar()) > '9' || ch < '0') if(ch == '-') f = -1;
	while(ch >= '0' && ch <= '9') x = x*10+(ch^'0'),ch = getchar();
	x *= f;
}

const int N = 1e5+5,M = 1e9;

struct segment
{
	public:
		struct smt{int l,r,s;}tree[N*50];
		int tot;
		void modify(int &x,int pre,int l,int r,int p)
		{
			x = ++tot;
			tree[x].l = tree[pre].l,tree[x].r = tree[pre].r,tree[x].s = tree[pre].s+p;
			if(l == r) return ;
			int mid = (l+r)/2;
			if(p <= mid) modify(tree[x].l,tree[pre].l,l,mid,p);
			else modify(tree[x].r,tree[pre].r,mid+1,r,p);
		}
		int query(int u,int v,int l,int r,int ql,int qr)
		{
			if(ql <= l && r <= qr) return tree[u].s-tree[v].s;
			int mid = (l+r)/2,ret = 0;
			if(ql <= mid) ret += query(tree[u].l,tree[v].l,l,mid,ql,qr);
			if(qr > mid) ret += query(tree[u].r,tree[v].r,mid+1,r,ql,qr);
			return ret;
		}
}ss;

int n,q,a[N],rt[N];

int main()
{
	read(n);
	for(int i = 1;i <= n;i++) read(a[i]),ss.modify(rt[i],rt[i-1],1,M,a[i]);
	read(q);
	while(q--)
	{
		int l,r; read(l); read(r);
		for(int ret = 1;;)
		{
			int t = ss.query(rt[r],rt[l-1],1,M,1,ret);
			if(t >= ret) ret = t+1;
			else {printf("%d\n",ret); break;}
		}
	}
	return (0-0); // QwQ
}