C08 可持久化线段树（主席树）

视频链接

#include <bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid (l + r) / 2
const int N = 2e5 + 10;
const int inf = 1e9;
struct node { int ls, rs, siz; } tr[N * 40];
int trlen, rt[N];
int a[N];

void insert(int pre, int& now, int l, int r, int val) {
    now = ++trlen;
    tr[now] = tr[pre]; // 复制上一个版本
    tr[now].siz = tr[pre].siz + 1; // 新增一个节点
    if (l == r) return; // 叶子节点，无需继续
    if (val <= mid) insert(lc(pre), lc(now), l, mid, val);
    else insert(rc(pre), rc(now), mid + 1, r, val);
}

int query(int pre, int now, int l, int r, int k) {
    if (now == pre) return 0; // 无变化，返回0
    if (l == r) return l; // 找到第k小的值
    int siz = tr[lc(now)].siz - tr[lc(pre)].siz; // 左子树元素个数
    if (k <= siz) return query(lc(pre), lc(now), l, mid, k);
    else return query(rc(pre), rc(now), mid + 1, r, k - siz);
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lu", &a[i]);
    trlen = 0;
    for (int i = 1; i <= n; i++) insert(rt[i - 1], rt[i], 0, inf, a[i]); // 构建可持久化线段树
    for (int i = 1, l, r, k; i <= m; i++) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(rt[l - 1], rt[r], 0, inf, k)); // 查询[l,r]第k小
    }
    return 0;
}

教学版，不推荐

C08 可持久化线段树（主席树）（另一个版本）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + N;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid (l + r) / 2
struct node { int ls, rs, l, r, siz; } tr[N * 2 * int(log2(N) + 1)];
int trlen, rt[N], a[N], b[N];

void pushup(int x) { tr[x].siz = tr[lc(x)].siz + tr[rc(x)].siz; }

int bt(int l, int r) { // 构建空树（离散化后的值域）
    int p = ++trlen; tr[p] = {0, 0, l, r, 0};
    if (l < r) {
        lc(p) = bt(l, mid);
        rc(p) = bt(mid + 1, r);
    }
    return p;
}

int change(int pre, int l, int r, int x) { // 插入新值
    int p = ++trlen; tr[p] = tr[pre]; // 复制上一版本
    if (l == r) { tr[p].siz++; return p; } // 叶子节点，增加计数
    if (x <= mid) lc(p) = change(lc(pre), l, mid, x);
    else rc(p) = change(rc(pre), mid + 1, r, x);
    pushup(p); return p;
}

int query(int pre, int now, int l, int r, int k) { // 查询第k小
    if (l == r) return l;
    int siz = tr[lc(now)].siz - tr[lc(pre)].siz; // 左子树元素个数差
    if (k <= siz) return query(lc(pre), lc(now), l, mid, k);
    else return query(rc(pre), rc(now), mid + +1, r, k - siz);
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = i; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1); // 离散化
    int bn = unique(b + 1, b + n + 1) - b - 1;
    unordered_map<int, int&> mp; // 映射原数到离散化后的值
    for (int i = 1; i <= bn; i++) mp[b[i]] = i;
    trlen = 0; rt[0] = bt(1, bn); // 构建空树
    for (int i = 1; i <= n; i++) rt[i] = change(rt[i - 1], 1, bn, mp[a[i]]); // 插入每个元素
    while (m--) {
        int l, r, k; scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", b[query(rt[l - 1], rt[r], 1, bn, k)]); // 输出原数值
    }
    return 0;
}

C50 【模板】可持久化线段树 P3834 静态区间第 k 小

视频链接

C104 【模板】整体二分+树状数组 P3834 可持久化线段树2

视频链接

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200005;
int n, m, cnt;     // cnt:原数个数+查询个数 // s:树状数组
int ans[N], s[N];
struct Q {
    // 原数: x位置，y值，k=0，id=0，opt=0
    // 查询: [x,y]第k小，id编号，opt=1
    int x, y, k, id, opt;
} q[N << (1)], q1[N << (1)], q2[N << (1)];

void add(int x, int v) { // 树状数组单点更新
    while (x <= n) s[x] += v, x += x & (-x);
}

int sum(int x) { // 树状数组前缀和
    int t = 0;
    while (x) t += s[x], x -= x & (-x);
    return t;
}

void solve(int l, int r, int L, int R) { // 整体二分主函数
    if (l > r) return; // [l,r]数据区间 [L,R]值域
    if (L == R) { // 找到答案
        for (int i = l; i <= r; i++)
            if (q[i].opt) ans[q[i].id] = L; // 记录查询答案
        return;
    }
    int mid = (L + R) >> 1, p1 = 0, p2 = 0; // 中间值，左右子区间指针
    for (int i = l; i <= r; i++) { // 按mid分流
        if (!q[i].opt) { // 原数，按值分流
            if (q[i].y <= mid)
                add(q[i].x, 1), q1[++p1] = q[i]; // 加入左区间
            else q2[++p2] = q[i]; // 加入右区间
        } else { // 查询，按个数分流
            int s = sum(q[i].y) - sum(q[i].x - 1); // [x,y]元素个数
            if (s >= q[i].k) q1[++p1] = q[i]; // 左区间
            else q[i].k -= s, q2[++p2] = q[i]; // 右区间
        }
    }
    // 恢复树状数组状态
    for (int i = 1; i <= p1; i++)
        if (!q1[i].opt) add(q1[i].x, -1);
    // 合并区间
    for (int i = 1; i <= p1; i++) q[i + l - 1] = q1[i];
    for (int i = 1; i <= p2; i++) q[i + l + p1 - 1] = q2[i];
    // 递归处理左右区间
    solve(l, l + p1 - 1, L, mid);
    solve(l + p1, r, mid + 1, R);
}

int main() {
    scanf("%d%d", &n, &m);
    int mi = 2e9, mx = -2e9, x, y, k;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        q[++cnt] = {i, x, 0, 0, 0}; // 原数
        mi = min(mi, x), mx = max(mx, x);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &k);
        q[++cnt] = {x, y, k, i, 1}; // 查询
    }
    solve(1, cnt, mi, mx); // 整体二分
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

这个题除了主席树（可持久化线段树），还可以使用整体二分。下面我将在这篇文章中介绍整体二分。

请注意，整体二分是离线算法，不能处理强制在线的问题。

二分答案

这一章节并不是讲二分答案算法的，所以即使你会二分答案也请看完。

整体二分的基础是二分答案。考虑如下问题：

给定整数序列 $a_1,a_2,\dots,a_n$，求其中第 $k$ 小的元素。

尽管这是一个十分简单的问题，但我们依然可以对其进行大炮打蚊子。抛开简单的 sort 和 nth_element 方法不谈，我们考虑对这个问题进行二分答案。

众所周知，想进行二分答案，我们必须将这个问题转化为一个最优化问题。于是我们把题意写成这样：

求一个最小的整数 $x$，使得序列中 $\le x$ 的数的数量 $\ge k$。

可以证明求出的 $x$ 就是序列的第 $k$ 小元素。

然后，就有了一份简单的二分答案代码：

bool OK(int x) // 判断是否满足 <=x 的数的数量 >=k 
{
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (a[i] <= x) ++cnt; // 统计数量 
	return cnt >= k; // 判断合法性 
}
void binarySearch(int low, int high) // high,low 为上下界 
{
	while (low < high)
	{
		int mid = (low + high) >> 1; // 取出 mid
		if (OK(mid)) high = mid; // 保留合法解 
		else low = mid + 1; // 去除不合法 x 
	}
	return low; // 此时 low == high，输出即可 
}

对二分答案算法就不做过多解释了，大家可以自行上网查询，相关资料还是很多的。

我们考虑将这份代码写成递归形式：

void binarySearch(int low, int high)
{
	if (low == high) // 递归一定要记得判终止条件 
	{
		ans = low;
		return;
	}
	
	int mid = (low + high) >> 1; // 取出 mid 
	
	// 将合法性判断直接放在 binarySearch 函数里 
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (a[i] <= mid) ++cnt;
	
	if (cnt >= k) binarySearch(low, mid); // 递归调用 
	else binarySearch(mid + 1, high);
}

这份代码还是比较简单的，只是把原先的 while 循环改成了递归调用处理。

我们发现这份代码还可以优化。在合法性判断中，代码枚举了整个序列，但实际上这个序列上有一部分元素在之前的二分排除的过程中可以被排除，无需重复计算。

上面那段话可能比较抽象，我们来看一个实际的例子：

$n=6$，$\{a_n\}=1,1,4,5,1,4$，$k=3$。

初始时 $low=1,high=5$，取出 $mid=3$。计算得序列中 $\le3$ 的元素数量为 $3\ge k$，因此往较小的一半递归，即新的 $[low,high]=[1,3]$。

此时值为 $4,5$ 的元素已经被排除了，不会再参与 $cnt$（$\le mid$ 元素数量）的统计，因此我们可以将它们剔除，此后不再参与 $cnt$ 的计算。

第二个例子：

$n=6$，$\{a_n\}=1,1,4,5,1,4$，$k=4$。

类似地，取出 $mid=3$ 后，发现序列中 $\le3$ 的元素数量为 $3<k$，要往大的一半递归。此时我们发现，在新的 $[low,high]=[4,5]$ 中，无论是哪个数 $x$，$\le3$ 的元素（$1$）都会计入 $\le x$ 的数的数量，因此我们可以仿照线段树上二分，令 $k\leftarrow k-cnt$，以此来省略这些元素的统计。

剔除元素的方法也很多，我的做法是改变元素在数组中存储的位置，将值 $\le mid$ 的元素存储在数组靠前的位置，$>mid$ 的元素存储在数组靠后的位置，然后递归时只保留一段区间的元素即可。

参考代码：

void binarySearch(int low, int high, int st, int ed) // st,ed 表示经剔除之后需要考虑的元素下标区间
{
	if (low == high)
	{
		ans = low;
		return;
	}
	int mid = (low + high) >> 1;
	int cnt = 0,n1 = 0,n2 = 0; // n1,n2 表示 <=mid >mid 的元素数量 
	for (int i = st; i <= ed; ++i)
		if (a[i] <= mid) ++cnt,v1[++n1] = a[i]; // 存储在 v1 中
		else v2[++n2] = a[i]; // 存储在 v2 中
	
	// 还原回原序列，改变位置
	for (int i = 1; i <= n1; ++i) a[st + i - 1] = v1[i];
	for (int i = 1; i <= n2; ++i) a[ed - n2 + i] = v2[i];
	
	// 递归调用 
	if (cnt >= k) binarySearch(low, mid);
	else k -= cnt,binarySearch(mid + 1, high);
	//   ^ 易错点：k -= cnt 容易漏掉
}

这个优化其实并没有太大的效果，因为其最坏情况下复杂度仍为 $O(n\log V)$（$V$ 为值域），一种最坏情况的构造就是所有元素都相等的序列。但是，优化后的二分答案框架对我们的整体二分算法有非常大的启发作用。

整体二分

接下来开始就是整体二分算法的解释了。回到原问题：

$m$ 次问询，每次给定区间 $[l,r]$，求序列 $a_l,a_{l+1},\dots,a_r$ 中第 $k$ 小的元素。

根据上面的分析，我们可以对每个问询进行一次二分，时间复杂度 $O(mn\log V)$。

于是我们开始思考这个算法慢在哪儿。发现每次二分我们都对所有 $n$ 个元素进行了 $O(\log V)$ 次分区。分区指将元素分为低区（$x\le mid$）和高区（$x>mid$）。

大量分区会导致算法的效率较低，但我们注意到每次二分，分区的情况总是固定的，因为元素的值是固定的。所以我们考虑对所有问询做一次二分，这样就能大大降低分区所消耗的时间了。

于是就有了整体二分。注意到不仅点需要分区，问询也会分区。一个问询在二分答案时向低区递归，就称它属于低区，否则称它属于高区。

考虑将点和问询储存在同一数组里，同时进行分区，可以写出如下代码：

struct Operation {int iQ,x,y,k;} op[N * 2],o1[N * 2],o2[N * 2];
/* 定义操作（加点或问询）
加点操作只使用 x（数组位置）、y（数值），iQ == 0
问询操作使用 [x,y] 表示区间 [l,r]，iQ 为问询编号，k 为问询中 k
*/

// 二分框架大致与之前的相同
void binarySearch(int low, int high, int st, int ed)
{
	if (st > ed) return; // 排除没有任何操作的区间，稍后会分析时间复杂度
	if (low == high) return;
	int mid = (low + high) >> 1,n1 = 0,n2 = 0;
	for (int i = st; i <= ed; ++i)
		if (!op[i].iQ)
			if (op[i].y <= mid) o1[++n1] = op[i];
			else o2[++n2] = op[i];
		else
		{
			int cnt = /**/;
			if (cnt >= op[i].k) o1[++n1] = op[i];
			else op[i].k -= cnt,o2[++n2] = op[i];
		}
	for (int i = 1; i <= n1; ++i) op[st + i - 1] = o1[i]; // 分区还原到原数组中
	for (int i = 1; i <= n2; ++i) op[ed - n2 + i] = o2[i];
	binarySearch(low, mid, st, ed - n2); // 两边都要递归
	binarySearch(mid + 1, high, st + n1, ed);
}

其中并未加入统计答案的部分，只实现了分区。对代码略作解释：分区和原来基本相同，使用两个临时数组记录，高区和低区都可能有问询，都需要递归处理。

上面那段代码里，$cnt$ 的计算还未写出，考虑如何计算。对问询 $[l,r,k]$，$cnt$ 的含义是 $[l,r]$ 区间内低区点的个数。所以我们可以先进行所有加点操作，维护一个区间和，然后处理问询时直接进行区间和查询即可。这可以使用树状数组（BIT）维护，不会的可以去这里。

然后我们添加 BIT，新的代码：（add 表示点增加，psq 表示前缀查询）

struct Operation {int iQ,x,y,k;} op[N * 2],o1[N * 2],o2[N * 2];
void binarySearch(int low, int high, int st, int ed)
{
	if (st > ed) return;
	if (low == high) return;
	int mid = (low + high) >> 1,n1 = 0,n2 = 0;
	for (int i = st; i <= ed; ++i)
		if (!op[i].iQ)
			if (op[i].y <= mid) add(op[i].x, 1),o1[++n1] = op[i];
			else o2[++n2] = op[i];
		else
		{
			int cnt = psq(op[i].y) - psq(op[i].x - 1);
			if (cnt >= op[i].k) o1[++n1] = op[i];
			else op[i].k -= cnt,o2[++n2] = op[i];
		}
	for (int i = 1; i <= n1; ++i) if (!o1[i].iQ) add(o1[i].x, -1); // 注意清空 BIT
	for (int i = 1; i <= n1; ++i) op[st + i - 1] = o1[i];
	for (int i = 1; i <= n2; ++i) op[ed - n2 + i] = o2[i];
	binarySearch(low, mid, st, ed - n2);
	binarySearch(mid + 1, high, st + n1, ed);
}

使用完 BIT 之后需要清空。

接着，我们还需要考虑如何统计答案。如果一个区间满足 low == high，那么区间内问询的答案就唯一确定了，直接记录即可。

直接放代码：

if (low == high)
{
	for (int i = st; i <= ed; ++i) ans[op[i].iQ] = low;
	return;
}

理论上应当有一个 if (op[i].iQ)，不过修改 $ans[0]$ 的值也不会对程序运行结果造成影响。

于是我们就完成了这道题目。完整代码：（时间复杂度分析在代码之后）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
int nPos,nQ,nOp,ans[N],bit[N];
struct Operation {int iQ,x,y,k;} op[N * 2],o1[N * 2],o2[N * 2];

// 树状数组（BIT）
int LSB(int x) {return x & -x;}
void add(int x, int z)
{
	while (x <= nPos)
	{
		bit[x] += z;
		x += LSB(x);
	}
}
int psq(int x)
{
	int ret = 0;
	while (x)
	{
		ret += bit[x];
		x -= LSB(x);
	}
	return ret;
}

void binarySearch(int low, int high, int st, int ed) // 整体二分模板
{
	if (st > ed) return;
	if (low == high)
	{
		for (int i = st; i <= ed; ++i) ans[op[i].iQ] = low;
		return;
	}
	int mid = (low + high) >> 1,n1 = 0,n2 = 0;
	for (int i = st; i <= ed; ++i)
		if (!op[i].iQ)
			if (op[i].y <= mid) add(op[i].x, 1),o1[++n1] = op[i];
			else o2[++n2] = op[i];
		else
		{
			int cnt = psq(op[i].y) - psq(op[i].x - 1);
			if (cnt >= op[i].k) o1[++n1] = op[i];
			else op[i].k -= cnt,o2[++n2] = op[i];
		}
	for (int i = 1; i <= n1; ++i) if (!o1[i].iQ) add(o1[i].x, -1);
	for (int i = 1; i <= n1; ++i) op[st + i - 1] = o1[i];
	for (int i = 1; i <= n2; ++i) op[ed - n2 + i] = o2[i];
	binarySearch(low, mid, st, ed - n2);
	binarySearch(mid + 1, high, st + n1, ed);
}

int main()
{
	scanf("%d%d", &nPos, &nQ);
	for (int i = 1; i <= nPos; ++i) // 处理每一个位置
	{
		int h;
		scanf("%d", &h);
		op[i] = (Operation){0, i, h, 0};
	}
	for (int iQ = 1; iQ <= nQ; ++iQ) // 处理每一个询问
	{
		int l,r,k;
		scanf("%d%d%d", &l, &r, &k);
		op[nPos + iQ] = (Operation){iQ, l, r, k};
	}
	binarySearch(0, 1e9, 1, nOp = nPos + nQ); // 整体二分
	for (int iQ = 1; iQ <= nQ; ++iQ) printf("%d\n", ans[iQ]); // 输出答案
	return 0;
}

时间复杂度分析

实际上，这道题还没有做完，我们还没有证明其时间复杂度正确性。容易发现整体二分外都是 $O(n)$ 的，所以着重看整体二分。

整体二分总共会进行 $\log V$ 层。每一个点或询问都只属于低区、高区之一，而没有操作的区间会进行排除，故总共运行 binarySearch() 函数的次数不会超过 $O((m+n)\log V)$。再乘上 BIT 的 $O(\log n)$ 复杂度，总时间复杂度为：

$O\Large(\normalsize(m+n)\log n\log V\Large)$

完结撒花。

整体二分代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
struct node{int l,r,k,id,op;}q[N],q1[N],q2[N];
int a[N],ans[N],b[N],c[N],n,m;
void add(int x,int k){for(;x<=n+m;x+=x&-x)c[x]+=k;}
int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
void solve(int l,int r,int L,int R)
{
	if(L>R)return;
	if(l==r)
	{
		for(int i=L;i<=R;i++)ans[q[i].id]=l;
		return ;
	}
	int mid=(l+r)>>1,p1=0,p2=0;
	for(int i=L;i<=R;i++)
	{
		if(!q[i].op)
		{
			if(q[i].l<=mid)add(q[i].r,1),q1[++p1]=q[i];
			else q2[++p2]=q[i];
		}
		else
		{
			int sum=get(q[i].r)-get(q[i].l-1);
			if(sum>=q[i].k)q1[++p1]=q[i];
			else q[i].k-=sum,q2[++p2]=q[i];
		}
	}
	for(int i=1;i<=p1;i++)if(!q1[i].op)add(q1[i].r,-1);
	for(int i=1;i<=p1;i++)q[i+L-1]=q1[i];
	for(int i=1;i<=p2;i++)q[i+L+p1-1]=q2[i];
	solve(l,mid,L,L+p1-1);solve(mid+1,r,L+p1,R);
	
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		q[i]={x,i,0,0,0};
	}
	for(int i=1;i<=m;i++)
	{
		int l,r,x;cin>>l>>r>>x;
		q[i+n]={l,r,x,i,1};
	}
	solve(0,1e9,1,n+m);
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}