数据结构进阶 | 可持久化数据结构

参考《算法竞赛进阶指南》、AcWing题库

可持久化数据结构

到目前为止, 我们学习的数据结构维护的都是 “数据集的最新状态”。若想知道数据集在任意时间的历史状态 (即 $\forall i \in[1, M]$, 执行完操作序列中第 $i$ 项操作后数据集的状态), 一种朴素的做法是 $\forall i \in[1, M]$, 在第 $i$ 项操作结束后, 把整个数据结构拷贝一遍, 存储在 $history[i]$ 中, 多耗费 $M$ 倍的空间。“可持久化” 提供了一种思想, 在每项操作结束后, 仅创建数据结构中发生改变的部分的副本, 不拷贝其他部分。这样一来, 维护数据结构的时间复杂度没有增加, 空间复杂度仅增长为与时间同级的规模。换言之, 可持久化数据结构能够高效地记录一个数据结构的所有历史状态。

可持久化 Trie

与 Trie 的节点一样, 可持久化 Trie 的每个节点也有若干字符指针指向子节点, 可以用 $trie[x, c]$ 保存节点 $x$ 的字符指针 $c$ 指向的子节点的编号 (0 代表指向空)。可持久化 Trie 按照以下步骤插入一个新的字符串 $s$ :

1. 设当前可持久化 Trie 的根节点为 $root$ , 令 $p=root$, $i=0$ 。
2. 建立一个新的节点 $q$, 令 $\operatorname{root}^{\prime}=q$ 。
3. 若 $p \neq 0$, 则对于每种字符 $c$, 令 $\operatorname{trie}[q, c]=\operatorname{trie}[p, c]$ 。
4. 建立一个新的节点 $q^{\prime}$, 令 $trie\left[q, s_{i}\right]=q^{\prime}$ 。换言之, 除了字符指针 $s_{i}$ 不同之外, 节点 $q$ 与节点 $p$ 的其他信息完全相同。
5. 令 $p=\operatorname{trie}\left[p, s_{i}\right], q=\operatorname{trie}\left[q, s_{i}\right], i=i+1$ 。
6. 重复步骤 $3 \sim 5$, 直至 $i$ 到达字符串末尾。

从 $root$ 出发沿着字符指针向下能够访问到的节点构成插入 $s$ 之前的 Trie, 而从 $root$ 出发沿着字符指针向下能够访问到的节点构成插入 $s$ 之后的 Trie。下图展示了在可持久化 Trie 中依次插入字符串 cat, rat, cab, fry 的过程。

可以看出, 可持久化 Trie 的本质是一张有向图。我们把每次揷入字符串后得到的新的根节点记录在数组 $\operatorname{root}[1 \sim 4]$ 中, 那么在可持久化 Trie 中从 $\operatorname{root}[i]$ 出发能够访问到的点和字符指针就组成了由前 $i$ 个字符串构成的 Trie。如下图所示。

构建可持久化 Trie 所需的空间和时间复杂度都是字符串的总长度的线性函数。

---

256. 最大异或和

给定一个非负整数序列 $a$，初始长度为 $N$。

有 $M$ 个操作，有以下两种操作类型：

1. A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 增大 $1$。
2. Q l r x：询问操作，你需要找到一个位置 $p$，满足 $l \le p \le r$，使得：$a[p]\ xor\ a[p+1]\ xor\ …\ xor\ a[N]\ xor\ x$ 最大，输出这个最大值。

输入格式

第一行包含两个整数 $N，M$，含义如问题描述所示。

第二行包含 $N$ 个非负整数，表示初始的序列 $A$。

接下来 $M$ 行，每行描述一个操作，格式如题面所述。

输出格式

每个询问操作输出一个整数，表示询问的答案。

每个答案占一行。

数据范围

$N,M \le 3 \times 10^5, 0 \le a[i] \le 10^7$。

输入样例：

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4 
Q 5 7 0 
Q 3 6 6 

输出样例：

4
5
6 

算法分析

异或前缀和：设 $s[i]$ 表示序列 $a$ 的前 $i$ 个数 $xor$ 起来得到的结果。特别地, 设 $s[0]=0$ 。

根据异或运算的性质：

$a[p] \;xor\; a[p+1] \; xor\; \cdots \;xor\; a[N] \;xor\; x=s[p-1] \;xor\; s[N] \;xor\; x$

对于 “添加操作”, 序列 $s$ 很容易维护。对于 “询问操作”, 问题变为: 已知一个 整数 $v a l=s[N] \;xor\; x$, 求一个位置 $p$, 满足 $l-1 \leq p \leq r-1$, 使得 $s[p] \;xor\; val$ 最大。

如果不考虑 $l-1$ 和 $r-1$ 的限制, 那么就是初始有 $N+1$ 个数 $s[0] \sim s[N]$, 每次操作可以 “在末尾添加一个数 $s[N+1]=s[N] \;xor\; x$ 并令 $N$ 增大 1 ” 或者 “询问序列 $s$ 中的哪个数与 $v a l$ 异或的结果最大”。我们在 “Trie” 的例题 The XOR Largest Pair 中已经讨论过类似问题的解法。只需把序列 $s$ 的每个数看作二进制数, 以字符串的形式插入 Trie, 询问时在 Trie 中优先尝试访问与 $val$ 的每一位相反的指针即可, 请读者回顾。

如果只有 $p \leq r-1$ 的限制, 那么只需用可持久化 Trie 代替上述解法中的 Trie。因为可持久化 Trie 保存了 $\forall i \in[0, N], s[0 \sim i]$ 这 $i+1$ 个二进制数构成的 Trie, 所以每次询问从 $\operatorname{root}[r-1]$ 出发, 优先尝试访问与 val 的每一位相反的指针即可。

回到原题, 为了要满足 $l-1 \leq p \leq r-1$, 我们可以在可持久化 Trie 的每个节点上增加一些信息。设 $e n d[x]$ 表示可持久化 Trie 的节点 $x$ 是序列 $s$ 中第几个二进制数的末尾节点 (若不是末尾节点, $end[x]=-1$ )。设 $latest[x]$ 表示在可持久化 Trie 以 $x$ 为根的子树中 $end$ 的最大值。从 $\operatorname{root}[r-1]$ 出发检索 $val$ 时, 仅考虑 $latest$ 值不小于 $l-1$ 的节点即可。整个算法的时间复杂度为 $O\left((N+M) \log 10^{7}\right)$ 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 600010;
int trie[N * 24][2], latest[N * 24]; // latest和end可合并为一个数组
int s[N], root[N], n, m, tot;

// 本题需要统计子树latest，故使用递归插入
// 插入s[i]，当前为s[i]的第k位
void insert(int i, int k, int p, int q) {
	if (k < 0) {
		latest[q] = i;
		return;
	}
	int c = s[i] >> k & 1;
	if (p) trie[q][c ^ 1] = trie[p][c ^ 1];
	trie[q][c] = ++tot;
	insert(i, k - 1, trie[p][c], trie[q][c]);
	latest[q] = max(latest[trie[q][0]], latest[trie[q][1]]);
}

int ask(int now, int val, int k, int limit) {
	if (k < 0) return s[latest[now]] ^ val;
	int c = val >> k & 1;
	if (latest[trie[now][c ^ 1]] >= limit)
		return ask(trie[now][c ^ 1], val, k - 1, limit);
	else
		return ask(trie[now][c], val, k - 1, limit);
}

int main() {
	cin >> n >> m;
	latest[0] = -1;
	root[0] = ++tot;
	insert(0, 23, 0, root[0]);
	for (int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		s[i] = s[i - 1] ^ x;
		root[i] = ++tot;
		insert(i, 23, root[i - 1], root[i]);
	}
	for (int i = 1; i <= m; i++) {
		char op[2]; scanf("%s", op);
		if (op[0] == 'A') {
			int x; scanf("%d", &x);
			root[++n] = ++tot;
			s[n] = s[n - 1] ^ x;
			insert(n, 23, root[n - 1], root[n]);
		}
		else {
			int l, r, x; scanf("%d%d%d", &l, &r, &x);
			printf("%d\n", ask(root[r - 1], x ^ s[n], 23, l - 1));
		}
	}
}

Solution

#include <iostream>
using namespace std;

const int N = 600010, M = 25 * N;

int n, m;
int sum[N];
int trie[M][2], maxId[M], idx;
int root[N];

void insert(int i, int k, int p, int q) {
    if (k < 0) {
        maxId[q] = i;
        return;
    }
    
    int c = sum[i] >> k & 1;
    if (p) trie[q][c ^ 1] = trie[p][c ^ 1];
    trie[q][c] = ++idx;
    insert(i, k - 1, trie[p][c], trie[q][c]);
    maxId[q] = max(maxId[trie[q][0]], maxId[trie[q][1]]);
}

void insert(int i, int p, int q) {
    maxId[q] = i;
    for (int k = 23; k >= 0; --k) {
        int c = sum[i] >> k & 1;
        if (p) trie[q][c ^ 1] = trie[p][c ^ 1];
        trie[q][c] = ++idx;
        q = trie[q][c];
        p = trie[p][c];
        maxId[q] = i;
    }
}

int ask(int now, int val, int k, int limit) {
    if (k < 0) return sum[maxId[now]] ^ val;
    int c = val >> k & 1;
    if (maxId[trie[now][c ^ 1]] >= limit) {
        return ask(trie[now][c ^ 1], val, k - 1, limit);
    } else {
        return ask(trie[now][c], val, k - 1, limit);
    }
}

int ask(int nowRoot, int val, int limit) {
    int p = nowRoot;
    for (int i = 23; i >= 0; --i) {
        int c = val >> i & 1;
        if (maxId[trie[p][c ^ 1]] >= limit) p = trie[p][c ^ 1];
        else p = trie[p][c];
    }
    return sum[maxId[p]] ^ val;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    maxId[0] = -1;
    root[0] = ++idx;
    insert(0, 0, root[0]);
   
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        sum[i] = sum[i - 1] ^ x;
        root[i] = ++idx;
        insert(i, root[i - 1], root[i]);
    }
   
    char op[2];
    int l, r, x;
    while (m--) {
       cin >> op;
       if (op[0] == 'A') {
           cin >> x;
           ++n;
           sum[n] = sum[n - 1] ^ x;
           root[n] = ++idx;
           insert(n, root[n - 1], root[n]);
       } else {
           cin >> l >> r >> x;
           cout << ask(root[r - 1], sum[n] ^ x, l - 1) << endl;
       }
   }
}

可持久化线段树

基于可持久化 Trie 的思想, 我们很容易设计出多种数据结构的可持久化版本——前提是数据结构的 “内部结构” 在操作过程中不发生变化（例如平衡树的旋转就改变了平衡树的 “内部结构” ）。可持久化线段树, 又称函数式线段树, 是最重要的可持久化数据结构之一。

仍以区间最大值问题为例, 线段树的 “单点修改” 只会使 $O(\log N)$ 个 区间对应的节点发生更新。对于每个被更新的节点 $p$, 我们创建该节点的副本 $p^{\prime}$ 。只要 $p$ 不是叶子节点, $p$ 的左右子树之一必然发生了更新。不妨设发生更新的是 $p$ 的左子树 $l c$, 我们在 $l c$ 中递归, 返回时令 $p^{\prime}$ 的左子树为 $l c^{\prime}$, 令 $p^{\prime}$ 的右子树与 $p$ 的右子树相同, 然后更新节点 $p^{\prime}$ 上保存的区间最大值即可。下图展示了在一棵线段树中对位置 7 进行 “单点修改” 后, 产生的 $O(\log N)$ 个新节点。图中省略了区间最大值的信息。

因为可持久化线段树不再是一棵完全二叉树, 所以我们不能再用层次序编号, 而是改为直接记录每个节点的左、右子节点编号, 与 Trie 的字符指针类似。因为每次修改都会创建 $O(\log N)$ 个新节点, 所以可持久化线段树的空间复杂度为 $O(N+M \log N)$ 。为了节省空间, 我们不再记录每个节点代表的区间 $[l, r]$, 而是作为递归参数传递。下面的代码定义并在初始序列 $a$ 上创建了一棵可持久化线段树 (目前为止, 它还只是一棵普通的线段树 。

// 可持久化线段树，建树
struct SegmentTree {
    int lc, rc; // 左右子节点编号
    int dat; // 区间最大值
} tree[MAX_MLOGN];
int tot, root[MAX_M]; // 可持久化线段树的总点数和每个根
int n, a[MAX_N];

int build(int l, int r) {
    int p = ++tot;
    if (l == r) { 
		tree[p].dat = a[l]; 
		return p; 
	}

    int mid = (l + r) >> 1;
    tree[p].lc = build(l, mid);
    tree[p].rc = build(mid + 1, r);
    tree[p].dat = max(tree[tree[p].lc].dat, tree[tree[p].rc].dat);
    return p;
}
// 在main函数中
root[0] = build(1, n);

对于第 $i$ 次修改, 以可持久化线段树的第 $i-1$ 个版本为基础, 执行如上图所示的步骤。下面的代码实现了可持久化线段树的单点修改 $a[x]=v a l$ 。

// 可持久化线段树，单点修改
int insert(int now, int l, int r, int x, int val) {
    int p = ++tot;
    tree[p] = tree[now]; 
    if (l == r) {
        tree[p].dat = val; 
        return p;
    }

    int mid = (l + r) >> 1;
    if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, val);
    else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, val);

    tree[p].dat = max(tree[tree[p].lc].dat, tree[tree[p].rc].dat);
    return p;
}
// 在main函数中
root[i] = insert(root[i - 1], 1, n, x, val);

容易发现, 可持久化线段树维护了每次操作之后线段树的历史形态。 $\forall i \in[1, M]$, 从 $\operatorname{root}[i]$ 出发向下能够访问到的节点就构成了执行完前 $i$ 次修改操作时, 维护 $a$ 序列区间最大值的线段树。可持久化线段树的查询操作与一般线段树类似, 这里就不再赘述。

可持久化线段树难以支持大部分 “区间修改”。当一个节点下传延迟标记时, 一旦我们创建它左右子节点 $l c, r c$ 的副本 $l c^{\prime}, r c^{\prime}$ 并把标记更新, 那么所有依赖 $l c, r c$ 的 “线段树版本” 都要改为依赖 $l c^{\prime}, r c^{\prime}$, 甚至还要自底向上重新计算某些信息。这样的后果是灾难性的。在一些特殊的题目中, 可以使用 “标记永久化” 代替标记的下传, 但应用的局限性很大。可持久化线段树的 “区间修改” 不是我们讨论的重点, 学有余力的读 者可以尝试用可持久化线段树配合 “标记永久化”, 完成 HDOJ4348 To the Moon。

---

255. 第K小数

给定长度为 $N$ 的整数序列 $A$，下标为 $1 \sim N$。

现在要执行 $M$ 次操作，其中第 $i$ 次操作为给出三个整数 $l_i,r_i,k_i$，求 $A[l_i],A[l_i+1],…,A[r_i]$ (即 $A$ 的下标区间 $[l_i,r_i]$)中第 $k_i$ 小的数是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，表示整数序列 $A$。

接下来 $M$ 行，每行包含三个整数 $l_i,r_i,k_i$，用以描述第 $i$ 次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第 $k$ 小的数的数值。

每个结果占一行。

数据范围

$N \le 10^5, M \le 10^4,|A[i]| \le 10^9$

输入样例：

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3 

输出样例：

5
6
3 

算法分析

在《离线分治算法》中, 我们讨论了经典的 “区间第 $k$ 小数” 问题的整体分治算法, 其时间复杂度为 $O\left((N+M) \log ^{2} N\right)$, 空间复杂度为 $O(N+M)$ 。本题我们再来介绍三种在线算法, 并把重点放在可持久化线段树的解法上, 其他两种做法只作简单叙述。

解法一：归并树

在 $[1, N]$ 上建立一棵线段树, 区间 $[l, r]$ 对应的节点上保存一个长度为 $r-l+1$ 的数组, 存储 $A_{l}, A_{l+1}, \ldots, A_{r}$ 排序后的结果。我们只需一起执行线段树建树和归并排序的过程, 即可实现上述结构的构造。这也是 “归并树” 名称的由来。

对于每次询问 $l_{i}, r_{i}, k_{i}$, 区间 $\left[l_{i}, r_{i}\right]$ 在线段树上对应 $O(\log N)$ 个节点。这些节点保存的 $O(\log N)$ 个有序数组共同组成 $A$ 序列的第 $l_{i} \sim r_{i}$ 个数。我们在《离线分治算法》的 “基于值域的整体分治算法” 小节中讨论过 “求序列第 $K$ 小数” 的二分答案做法。对于本题的每个询问, 我们也二分答案 $\operatorname{mid}$, 然后在 $O(\log N)$ 个有序数组中分别二分查找最后一个 $\leq mid$ 的数所处的下标 $p$ 。$\Sigma p$ 即为 $A\left[l_{i} \sim r_{i}\right]$ 中 $\leq m i d$ 的数的个数, 与 $k_{i}$ 比较就可以确定二分答案上下界的变化情况。

该算法的时间复杂度为 $O\left(N \log N+M \log ^{3} N\right)$, 空间复杂度为 $O(N \log N)$, 且不能扩展到支持 “修改” 操作的动态 “区间第 $k$ 小数” 问题。

可持久化线段树

归并树解法的时间复杂度较高, 其原因在于线段树没有维护 “值域” 的划分信息, 需要经过两重二分才能与 $k_{i}$ 执行比较, 这启发我们在 “值域” 而不是 “下标”上建立线段树。

暂时不考虑 $l_{i}, r_{i}$ 。如果能够在线段树上维护 “序列 $A$ 有多少个数落在值域区间 $[L, R]$ 内” (记为 $c n t_{L, R}$ ), 那么只需比较 $c n t_{L, m i d}$ 与 $k_{i}$ 的大小关系, 即可确定 $A$ 的第 $k_{i}$ 小数是 $\leq mid$ 还是 $> mid$, 从而可以进入线段树的左、右子树之一。换言之, 线段树对值域的划分代替了对答案的二分, 请读者务必理解再继续阅读。在有 $l_{i}, r_{i}$ 限制的情况下, 我们可以使用可持久化线段树。

我们首先对 $A$ 序列进行离散化, 设离散化之后 $A[i]$ 的值为 $H[A[i]] \in [1, T]$ 。在区间 $[1, T]$ 上建立可持久化线段树, 线段树的每个节点上保存一个值 $c n t$, 表示该节点代表的值域区间 $[L, R]$ 中一共插入过多少个数, 起初 $c n t$ 值均为 0 。

然后我们对于每个 $A[i]$, 在可持久化线段树上执行 $H[A[i]]$ 的 “单点修改”, 将其 $c n t$ 加 1 。线段树每个内部节点的 $c n t$ 值等于左右子节点的 $c n t$ 值之和。

此时, 可持久化线段树中 “以 $\operatorname{root}[i]$ 为根的线段树” 的值域区间 $[L, R]$ 保存了 $A$ 的前 $i$ 个数有多少个落在值域 $[L, R]$ 内。

接下来考虑每个询问 $l_{i}, r_{i}, k_{i}$ 。有一条重要的性质：以 $\operatorname{root}\left[l_{i}\right]$ 和 $\operatorname{root}\left[r_{i}\right]$ 为根的两棵线段树对值域的划分是相同的。换言之, 除了 $c n t$ 值不同外, 两棵线段树的内部结构和每个节点代表的值域区间完全对应。这意味着: “ $\operatorname{root}\left[r_{i}\right]$ 的值域区间 $[L, R]$ 的 $cnt$ 值” 减去 “ $\operatorname{root}\left[l_{i}-1\right]$ 的值域区间 $[L, R]$ 的 $c n t$ 值” 就等于 $A\left[l_{i} \sim r_{i}\right]$ 中有多少个数落在值域 $[L, R]$ 内, 也就是可持久化线段树中两个代表相同值域的节点具有可减性。下面的代码同时从 $\operatorname{root}\left[l_{i}-1\right]$ 和 $\operatorname{root}\left[r_{i}\right]$ 出发执行 $O(\log N)$ 的访问, 利用上述可减性计算出询问的答案。

// 可持久化线段树，例题：POJ2104 K-th Number，查询部分
// 在p, q两个节点上，值域为 [l,r]，求第k小数
int ask(int p, int q, int l, int r, int k) {
    if (l == r) return l; // 找到答案
    int mid = (l + r) >> 1;
    // 有多少个数落在值域 [l,mid] 内
    int lcnt = tree[tree[p].lc].cnt - tree[tree[q].lc].cnt;
    if (k <= lcnt) return ask(tree[p].lc, tree[q].lc, l, mid, k);
    else return ask(tree[p].rc, tree[q].rc, mid + 1, r, k - lcnt);
}
// 在main函数中，询问为(li,ri,ki)
int ans = ask(root[ri], root[li - 1], 1, t, ki);

该算法的时间复杂度为 $O((N+M) \log N)$, 空间复杂度为 $O(N \log N)$ 。若要扩展到支持 “修改” 操作的动态 “区间第 $k$ 小数” 问题, 则需在最外层套一个树状数组, 不推荐这种做法 (空间复杂度较高), 故不再介绍。

解法三：线段树套平衡树

对序列 $A$ 离散化之后, 在值域 $[1, T]$ 上建立线段树, 在线段树的每个节点 $[L, R]$ 上建立一棵平衡树 $($ 例如 $T r e a p)$, 保存序列 $A$ 落在值域区间 $[L, R]$ 内的数的下标。因为平衡树本身支持查询 “ $\leq x$ 的数有多少个”, 所以我们也能知道序列 $A$ 的前 $x$ 个数有多少个落在值域区间 $[L, R]$ 内。

对于每个询问 $l_{i}, r_{i}, k_{i}$, 与解法二开头讨论的方式一样, 在线段树中进行访问。只需在线段树左子节点 $[L, m i d]$ 对应的平衡树中查询 $\leq r_{i}$ 和 $\leq l_{i}-1$ 的数的个数, 二者相减与 $k_{i}$ 比较, 即可确定应该递归进入线段的左子树还是右子树。

该算法的时间复杂度为 $O\left((N+M) \log ^{2} N\right)$, 空间复杂度为 $O(N \log N)$ 。因为平衡树本身支持插入和删除, 所以可以直接扩展到支持 “修改” 操作的动态 “区间第 $k$ 小 数” 问题。当把 $A[x]$ 赋值为 $y$ 时, 从包含 $A[x]$ 的值域区间对应的平衡树内删除下标 $x$, 在包含 $y$ 的值域区间对应的平衡树内插入下标 $x$ 即可。树套树也是解决此类动态问题的最传统解法。

可持久化线段树、树套树和离线分治算法还有许多广泛的应用, 例如: 可以用可持久化线段树实现 “可持久化数组”。

Solution

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

const int N = 100010, M = 10010;

int n, m;
int a[N];

int root[N], idx;
struct Node {
    int ls, rs;
    int cnt;
} tr[N * 4 + N * 17]; //N * 4 + NlogN

vector<int> nums;
int find(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r) {
    int p = ++idx; // p 新建一个点
    if (l == r) return p;
    
    int mid = l + r >> 1;
    tr[p].ls = build(l, mid);
    tr[p].rs = build(mid + 1, r);
    return p;
}

int insert(int now, int l, int r, int x) {
    int p = ++idx; // p 新建一个点
    tr[p] = tr[now]; // 复制现版本数据
    
    if (l == r) { //  l == x && r == x
        ++tr[p].cnt;
        return p;
    }
    
    int mid = l + r >> 1;
    
    if (x <= mid) tr[p].ls = insert(tr[now].ls, l, mid, x);
    else tr[p].rs = insert(tr[now].rs, mid + 1, r, x);
    
    tr[p].cnt = tr[tr[p].ls].cnt + tr[tr[p].rs].cnt;
    return p;
}

int ask(int q, int p, int l, int r, int k) {
    if (l == r) return r;
    
    int mid = l + r >> 1;
    // tr[tr[q].ls].cnt 是 q(root[r]) 版本中 在[l, mid]左半区间范围里的数个数
    // tr[tr[p].ls].cnt 是 p(root[l - 1]) 版本中 在[l, mid]左半区间范围里的数个数
    int cnt = tr[tr[q].ls].cnt - tr[tr[p].ls].cnt;
    if (k <= cnt) return ask(tr[q].ls, tr[p].ls, l, mid, k);
    else return ask(tr[q].rs, tr[p].rs, mid + 1, r, k - cnt);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        nums.push_back(a[i]);
    }
    // 离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    // 第0个版本的什么都没有就用build, build是建立好骨架, 每个版本insert改不同数据
    root[0] = build(0, nums.size() - 1);
    
    // 后面的每插入一个点算一个版本, 每次插入都只是比上一个版本多1个数
    // 左右参数给0和nums.size()-1是因为离散化之后的值域就是在0, nums.size()-1之间
    // 要插入必须得把这些地方全包才能保证找得到插入点 
    for (int i = 1; i <= n; ++i) {
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
    }
    
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        int id = ask(root[r], root[l - 1], 0, nums.size() - 1, k);
        cout << nums[id] << endl;
    }
}