# 倍增LCA
## 引子
什么？你还不知道什么是LCA？LCA就是树上两个节点的最近公共祖先。 
所以，对于怎么找LCA，是个人都会想到一个办法，让两个节点不断向上移动，只要重合了就是LCA了，嘿嘿嘿 
然鹅，一个一个移动太慢，只要数据过了 $10^8$ 分分钟 T 飞~ 
所以，我们需要一个快速的移动方式，比如，成几何级数的移动，这就是倍增算法 

## 基本思路 
既然要成几何级数的移动速度，要找个底数，比如2吧，每次移动 $2^k$ 个 
要想一次移动这么多，肯定要预处理，不如先预处理一个数组 $grand[i][j]$ 表示 $i$ 向上跳$$2^k$$个是谁，跳出这棵树的值就为-1吧 
怎么判断已经跳到了LCA呢？毕竟公共祖先不只有LCA一个 
不如就不直接跳到LCA，把所有跳到相同节点的情况都视为跳出树了，一直跳直到跳不动了为止，这时候两个节点的父节点就是LCA了，是不是特别机智~ 

## 预处理

怎么预处理出 $grand$数组呢？
什么？你想一个个往上跳，然后取对数？省省吧，有这功夫早就 T 飞了，我们需要一个更高效的方法，最好能利用已经求出的 $grand$ 数组 
那不就是动态规划嘛，让我们来凑一手状态转移方程 
首先，$i$ 向上跳 $2^k$ 个可以分解成两个动作，先向上跳 $2^{k-1}$ 个，再向上跳 $2^{k-1}$ 个 
$i$向上跳 $2^{k-1}$ 个不就是$grand[i][k-1]$嘛，套个娃，再向上跳 $2^{k-1}$ 个当然就是 $grand[grand[i][k-1]][k-1]$ 。于是我们得出方程：
$$
grand[i][k]=grand[grand[i][k-1]][k-1]
$$
瞅瞅这个方程，我们该用什么算法呢？ 
要想转移状态，必须要先求出 $grand[i][k-1]$，这告诉我们应该：
```cpp
for(int k=;k< MAXON;k++)
{
 //求grand
}
```
再看，我们还要先求出$i$的祖先节点的$grand$，因为我们要用到$grand[grand[i][k-1]][k-1]$ 嘛，这好说，来一手 $dfs$ 深度优先搜索就好了，顺便还可以记录每个节点的父节点和深度，一举两得 
于是我们竟然可以写出代码了
先用邻接表存图：
```cpp
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot=0;//总边数
	int grand[500010][30];
	int fa[MAXON];
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}
```
```cpp
void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i < = g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}
```

## 跳！
预处理好了，接下来就是跳了 
怎么跳呢？先跳到同一高度，然后什么都好说
```cpp
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA
```
这里为什么要有个step呢，因为先封个顶，一点点下降，能跳再跳，万一就跳出去了呢 
然后就是两个节点一起向上跳了
```cpp
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LC
```
要问这个$lg$数组是怎么来的？洛谷上抄的，嘿嘿嘿
```cpp
	for (int i = 1; i < = n; i++) //常数优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); //看不懂的可以手推一下
```

## 完整代码
我写这玩意的时候特别喜欢class，于是。。。码风奇丑，凑合着看吧。。。
```cpp
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXON = 1000010;
int dep[MAXON];//dep[i]代表编号为i的点所处的深度
int lg[MAXON];
class Graph
{
private:
	struct edge
	{
		int to;//这条边到达的点
		int next;//下一条边
	}Edge[MAXON];
	int head[MAXON];//head[i]表示由i开始的第一条边的编号
	int tot;//总边数
	int grand[500010][30];
	int fa[MAXON];
public:
	Graph()
	{
		tot = 0;
	}
	void add_dege(int from, int to)
	{
		tot++;//当前边的编号
		Edge[tot].to = to;
		if (from != -1)
			Edge[tot].next = head[from];//插入在前
		head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
	}
	void dfs(int from, int now)
	{
		fa[now] = from;//记录父节点
		int start = head[now];//从第一个子节点开始找
		if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
			dep[now] = dep[from] + 1;
		//int g = log2(dep[now]) ;
		int g = lg[dep[now]];
		if (from != -1)//根节点没有父节点
			grand[now][0] = from;//2^0=1,即父节点
		for (int i = 1; i <= g; i++)
		{
			grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
		}
		while (start)//一个一个找孩子
		{
			if (Edge[start].to == from)//若相连节点不是父节点
			{
				start = Edge[start].next;
				continue;
			}
			dfs(now, Edge[start].to);//继续搜索子节点
			start = Edge[start].next;//搜索下一个子节点
		}
	}
	int lca(int a, int b)
	{
		if (dep[a] > dep[b])//统一b深度大于a
		{
			a = a + b;//a此时等于原来的a,b之和
			b = a - b;//b此时等于原来的a
			a = a - b;//a此时等于原来的b
		}//神奇的交换方法
		int deep = dep[b] - dep[a];//深度差
		//int step = log2(deep);
		int step = lg[deep];//最大要走的步数
		for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
		{
			if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
			else
			{
				b = grand[b][i];//没跳过头,跳
			}
		}
		if (a == b) return a;//若相等,则已经找到LCA
		step = lg[dep[a]]; //要走的步数
		//step = log2(dep[a]);
		for (int i = step; i >= 0; i--)
		{
			if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
			else//没跳过头,跳
			{
				a = grand[a][i];
				b = grand[b][i];
			}
		}
		return fa[a];//最后他们的父节点就是LCA
	}
};
Graph G;
int main()
{
	int n, m, s;
	//cin >> n >> m >> s;
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= n; i++) //常熟优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); //看不懂的可以手推一下
	n--;
	while (n--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		G.add_dege(a, b);
		G.add_dege(b, a);
	}
	G.dfs(-1, s);
	while (m--)
	{
		int a, b;
		//cin >> a >> b;
		scanf("%d%d", &a, &b);
		int ans = G.lca(a, b);
		if (ans == -1)
			printf("%d\n", s);
		//cout << s << endl;
		else
			printf("%d\n", ans);
		//cout << ans << endl;
	}
	return 0;
}
```

倍增LCA

**这篇文章挺短的，因为我也不怎么会…(⊙_⊙;)…**
# 引子 
众所周知，用导数可以求一个函数的最值 
 
如果...要求的东西不是函数呢？ 
比如：
$$
a^2+b^2-2ab
$$
一般的做法肯定是均值不等式：
$$
a^2+b^2-2ab \ge 2ab-2ab =0
$$
但如果复杂到均值不等式做不了呢？ 
大佬：“那就来一把柯西，没有一把柯西搞不定的东西，如果有，就用两把！” 
 
当然，我们不是大佬，用一点蠢一点的办法，比如 **”偏微分“** 

# 栗子 
我们会求单变量函数的最值，能不能想办法把两个变量化成一个变量呢？ 
 
不如我们先把 $b$ 当成常数，如果无论 $b$ 取何值，$a$ 原式永远在 $a$取同一个值时取到最小值，那么当原式取到最小值时，$a$ 一定等于这个值 
$b$ 也是同理 
这样我们只要把这两个值肝出来，问题就解决了嘛q(≧▽≦q)，至于方法，肯定是求导啊 
看不懂？我们来试一下: 
 
先把$b$当成常数，求其导数：
$$
{\partial \over \partial a}\cdot (a^2+b^2-2ab)=2a-2b
$$
令其等于0:
$$
\Rightarrow a=b
$$
故$a=b$时原式取到最小值(需要讨论，此处省略) 
 
同样地，把$a$当成常数，求其导数：
$$
{\partial \over \partial b} (a^2+b^2-2ab)=2b-2a
$$
令其等于0：
$$
\Rightarrow a=b
$$
故$a=b$时原式取到最小值(需要讨论，此处省略) 
综上所述，$a=b$时原式取到最小值，为0 
 
注意到: $d\rightarrow \partial$ 了吗？$d$ 表示常微分，$\partial$ 表示偏微分(微的都不是单变量函数了，当然得换一个) 
至于为什么上面单独有一个$\partial$ ,那是因为右边那一坨太大了，怼上去不好看，所以单独拿出来，只留一个$\partial$ 在上面 

# 本质
还是看不懂，那让我们看看偏微分的本质 
 
函数为什么一定是一个单变量的呢？为什么不能有两个自变量呢？ 
当然可以，专业点，这个东西叫 **二元函数** 
 
既然是个函数，就可以化它的图像啦，不如看看$f(x,y)=x^2+y^2-2xy$的图像： 
![UH62DO.png](https://s1.ax1x.com/2020/07/22/UH62DO.png) 
这玩意变成一个立体图了！o((⊙﹏⊙))o.
联系一下一元函数取最值的情况——切线水平 
不难推测，二元函数取最值的情况是：**切面水平**
 
切面水平，怎么表示呢？ 
 
显然，如果一个平面和一个曲面相切，过切点的任何一个面截这两个面所得的直线和曲线一定相切，反之亦然 (此处不严谨) 
所以我们只要找两条直线就好啦~ 
所以我们只要找两个截面就行啦~ 
截面当然是沿x轴一个沿y轴一个最方便啦~ 
要问x轴上的截面截得的两条线的解析式当然令x等于一个固定值就行啦，y轴也一样~ 
![看不懂，没关系](https://s1.ax1x.com/2020/07/22/UHRxmV.png)
把x当成常数，导数就是这个曲面在沿x截面截得的曲线的切点的斜率随y变化的关系 
反之亦然 
我们只需要令这两个导数等于0，就确定了水平两条相交直线，并且这两条直线还与图像相切 
这样就确定了水平的切面 
进而就可以求出最大值 
 
以上部分看懂了最好，看不懂也没关系 （因为我写的也很绕$。\_。$）
但只要记住：
1. 把一个变量当常数，求导，令导数等于0，得到一条方程
2. 把另一个变量当常数，求导，令导数等于0，得到另一条方程
3. ......
4. 解这些方程，得到个个变量的值
5. 把这些值带入原式，得到最值(此处还需讨论一下)

就可以使用了

# 应用
有了这么强大的工具，我们干点什么好呢？ 
不如来推导一下回归直线的最小二乘法的公式~ 
 
有一堆点：
$$
(x_1,y_1) , (x_2,y_2) , (x_3,y_3) ... (x_n,y_n)
$$
设回归直线为
$$
y=ax+b
$$
那么原来的点在直线上就是：
$$
(x_1,ax_1+b) , (x_2,ax_2+b) , (x_3,ax_3+b) ... (x_n,ax_n+b) 
$$
纵坐标的方差(类似？)的n倍就是：
$$
\begin{aligned}
n\sigma^2 &=\sum_{i=1}^n (ax_i+b-y_i)^2=a^2\sum_{i=1}^n x_i^2+2ab\sum_{i=1}^nx_i-2a\sum_{i=1}^nx_iy_i+nb^2+\sum_{i=1}^ny_i^2-2b\sum_{i=1}^ny_i\\
&=a^2\sum_{i=1}^n x_i^2+2nab\overline x-2a\sum_{i=1}^nx_iy_i+nb^2+\sum_{i=1}^ny_i^2-2nb\overline y
\end{aligned}
$$
当其取到最小值时，偏导数为0
 
对$a$求偏导：
$$
{\partial (n\sigma^2)\over \partial a} = 2a\sum_{i=1}^nx_i^2+2nb\overline x-2\sum_{i=1}^nx_iy_i
$$
令其等于零：
$$
\Rightarrow a\sum_{i=1}^nx_i^2+nb\overline x-\sum_{i=1}^nx_iy_i=0·····(1)
$$
对$b$求偏导：
$$
{\partial (n\sigma^2)\over \partial b} = 2na\overline x+2nb-2n\overline y\\
$$
令其等于0：
$$
\Rightarrow a\overline x+b=\overline y \Rightarrow b=\overline y-a\overline x
$$
代入(1)式得：
$$
a\sum_{i=1}^nx_i^2+n\overline x(\overline y-ax\overline )-\sum_{i=1}^nx_iy_i=0\\
\Rightarrow a={\sum_{i=1}^n x_iy_i-n\overline x\overline y\over \sum_{i=1}^n x_i^2-n\overline x^2}
$$
推导完成，完结撒花 ✿✿ヽ(°▽°)ノ✿

偏微分

1. “我的学生都战死了，现在轮到我这个老师上去了！” 
1940年一名中央航空教练员驾驶飞机冲向32架日本轰炸机前留在日记本上的最后一句话 
 
2. “冲锋之势,有进无退,陷阵之志,有死无生”——三国•高顺 
“只解沙场为国死，何须马革裹尸还”——清•徐锡麟《出塞》 
“烈士不怕死，所死在忠贞。”——唐•柳宗元《韦道安》 
 
3. 伊卡洛斯（希腊文：Ίκαρος英文名称：Icarus）是希腊神话中代达罗斯的儿子，与代达罗斯使用蜡和羽毛造的翼逃离克里特岛时，他因飞得太高，双翼上的蜡遭太阳融化跌落水中丧生…… 
欲望淹于所及之高 
便会窒息 
 
4. 十五年过去了。我们 有了自己的三代机和四代机，我们有了自己的大飞机，我们有了自己的航母。还记得十五年前，南海上空的英灵吗？中国最大的幸运，就是永远有层出不穷的英雄；中国最大的不幸，就是永远匮乏铭记英雄们的人。让我们永远记住:有一个编号，叫做81192；有一个英雄，叫做王伟。 
 
5. 1940年5月，枣宜会战。他亲自率领部队与敌寇决战。在部队被敌层层包围的不利态势下，他身先士卒、冲锋在前、力战不退，与敌寇拼死搏杀，最后身中7弹，壮烈殉国的张自忠将军 
 
6. “人一旦堕落，上帝就会以最快的速度收走你的天赋和力量” ――蒋方舟

网易云论据

# 简介
主席树是一种数据结构，用来解决区间第k小(大)问题。要问为什么叫主席树？因为这是一个叫黄嘉泰的dalao发明的 ~~名字缩写跟我国某位主席一样，Orz~~ 
时间复杂度是Onlogn，十分优秀 ~~空间复杂度倒是有点大~~ 
# 前置姿势
## 权值线段树
+ 众所周知，权值线段树是一种线段树 ~~话说这不是废话吗2333~~
+ 它不同于一般线段树的是它的每一个结点的值代表这个区间中的数在序列中出现的总次数，正所谓“权值”
+ 它可以被用来处理区间第k小(大)问题

### 查询原理
此处利用二分的思想：
现有区间[l,r],不妨设区间[l,m] ( m为区间中间位置 ) 内的数的个数为n: 
显然: 
若 n < k ，第k小就是区间[m+1,r]的第 k - n 小
反之，则为区间[l,r]的第k小
于是可以写出伪代码
```cpp
int que(k,l,r)//询问区间[l,r]的第k小
{
 if(l==r) return l;
 int m=(l+r)/2;
 if(cnt(l,m)>=k) return que(k,l,m);
 return que(k-cnt(l,r),m+1,r);
}
```
#### 举个栗子
对于序列 1,3,2,2,0,1 建立的权值线段树如下
![](https://s1.ax1x.com/2020/06/02/tt4T3R.png) 
查询第3小： 
1. 访问区间[0,3],有6个数，> 3
2. 访问左区间[0,1]查询第3小,有3个数,=3
3. 访问右区间[1,1],查询第2小，返回结果->1

### 建树
当然是递归建树啦ψ(｀∇´)ψ 
此处同普通线段树,只需统计区间个数即可 
此处使用暴力统计 ~~其实是懒得打~~ 
```cpp
int ls[100],rs[100],cnt=0,v[100];
int l[100],r[100];
int num[100];
int n;
void update(int p)
{
 v[p]=v[ls[p]]+v[rs[p]];
}
void build(int p,int l,int r)
{
 l[p]=l;r[p]=r;
 if(l==r)
 {
 for(int i=0;i<n;i++)
 {
 if(num[i]>=l&&num[i]<=r) v[p]++;
 }
 return;
 }
 int m=l+r>>1;
 ls[p]=++cnt;
 rs[p]=++cnt;
 build(ls[p],l,m);
 build(rs[p],m+1,r);
 update(p);
}
```
### 查询
```cpp
int que(int p,int k)
{
 if(l[p]==r[p]) return l;
 int m=l[p]+r[p]>>1;
 if(v[p]<k) return que(rs[p],k-v[p]);
 return que(ls[p],k);
}
```
# 思想
权值线段树有一个缺点，只能查询整个区间的第k小，对于子区间就无能为力了 
那是不是对于所有子区间都能搞出一个权值线段树就好了呢？ 
## 前缀和
这里就可以用前缀和的思想： 
若用相同范围（即相同的l，r）对任意子区间建树，所有的权值线段树结构相同，这意味着两棵树可以相减（即每一个等位节点相减）！ 
于是我们可以依次对[0,0],[0,1],[0,2]...[0,n]建树，如需得到[l,r]的树，只需将[0,r]和[0,l-1]两棵线段树相减即可！ 
查询可以机智地使用宏定义 
```cpp
#define lv (value[ls[r]]-value[ls[l]])//相减后得到的线段树左儿子的值
#define rv (value[rs[r]]-value[rs[l]])//相减后得到的线段树右儿子的值
```
## 空间优化
然而这里有一个问题，每一个区间建立线段树，空间复杂度太大，无法接受 
怎么优化呢？ 
实际上，下一棵线段树就相当于上一棵线段树进行单点更新，即[0,n]相对于[0,n-1]只是更新了[num[n],num[n]]的值而已。 
由于主席树不是完全二叉树，需要开数组保存左右儿子的编号，这里利用一下：如果更新左儿子，就把右儿子编号赋为上一棵树该节点右儿子的编号，反之也一样。这样每次建树只需新开一条链就行了 ~~有没有感觉特别机智~~ 
更新
```cpp
void updata(int last/*上一棵线段树等位结点编号*/, int p, int v)//建立下一棵线段树,相当于线段树的单点更新,只需保存一条链而已
{
	ln[p] = ln[last]; rn[p] = rn[last];//这棵线段树和上一棵一样,直接赋值
	value[p] = value[last] + 1;//明显v包含在区间里,直接加一即可
	if (ln[p] == rn[p]) return;//叶节点,不用继续更新,直接返回即可
	if (v <= (ln[p] + rn[p] >> 1))//包含在左儿子的区间中
	{
		rs[p] = rs[last];//右子树(即右儿子)和上一棵线段树的一样
		ls[p] = ++cnt;//累计节点编号
		//本来更新节点的值是写在这里的,但这样根节点就更新不了了,于是写到了前面
		updata(ls[last], ls[p], v);//建立左子树
	}
	else//反之亦然同理
	{
		ls[p] = ls[last];
		rs[p] = ++cnt;
		updata(rs[last], rs[p], v);
	}
}
```
循环建树
```cpp
void build()//建立主席树
{
	root[0] = cnt;//0号根节点为空树,便于相减
	bud(0, n2 - 1, cnt);//先建一发空树
	for (int i = 0; i < n; i++)//[0,n)和(0,n]皆可,只不过是root[i-1]和root[i+1]的区别
	{
		root[i + 1] = ++cnt;//累计根节点
		updata(root[i], root[i + 1], num[i]);//更新这棵线段树
	}
}
```
## 离散化
然而还有一个问题，权值线段树的空间复杂度是与数据范围相关的，所以此处需要离散化。所谓离散化就是把一堆范围很大的数映射到一段很小的区间里 
例如对于序列：12 , 76 , 123 , 67 , 1 , 20 
排序后：1 , 12 , 20 , 67 , 76 , 123 
令：1->1 , 12->2 , 20->3 , 67->4 , 76->5 , 123->6 
原序列就变成了：2 , 5 , 6 , 4 , 1 , 3 
至于怎么搞映射？这不是map最擅长的吗（￣︶￣）↗　
```cpp
map <int, int> po/*由原值映射到离散化后的值*/, re/*由离散化后的值映射到原值*/;
sort(tmp, tmp + n);//先来一发排序
//巨坑!!tmp+n是排序区间末区间端点的下一个值的地址!!!
//我也不知道STL为什么要这样反正我就这样爆了两个点
n2 = unique(tmp, tmp + n) - tmp;//去重也一样!!!(STL的东西都是这个尿性)
for (int i = 0; i < n2; i++)//记录离散化后的数值
{
	po[tmp[i]] = i;
	re[i] = tmp[i];
}
for (int i = 0; i < n; i++)//将原值变为离散化后的值
{
	num[i] = po[num[i]];
}
```
输出答案时也别忘了搞回去
```cpp
cout << re[ans] << '\n';//输出答案,一定要离散化的数值搞回来!!!小心爆零!!!
```
# 完整代码
```cpp
/*
主席树 20191210
皮:震惊,cin和cout,竟然没有没有TLE???数据竟然没有爆int???!!!
*/
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
int ls[20000000]/*保存节点左儿子*/, rs[20000000]/*保存节点右儿子*/,
root[200010]/*保存第一个元素到第n个数对应权值线段树的根节点*/,
value[20000000]/*保存权值线段树节点的值*/, 
ln[20000000]/*保存节点区间左端点*/, rn[20000000]/*保存节点区间右端点*/;
int cnt/*累计节点编号*/, n/*数的个数*/;
int n2/*排序去重后数的个数(离散化巨坑)*/;
int num[200010]/*保存序列*/, tmp[200010]/*便于离散化*/;
void bud(int l, int r, int p)//建立空树(便于线段树相减),同普通线段树,只是没有保存节点权值而已
{
	ln[p] = l; rn[p] = r;//显然
	if (l != r)//巨坑,否则死循环!!!
	{
		ls[p] = ++cnt;//累计子节点
		bud(l, (l + r >> 1), cnt);//递归建立左子树
		rs[p] = ++cnt;//累计子节点
		bud((l + r >> 1) + 1, r, cnt);//递归建立右子树
	}
}
void updata(int last/*上一棵线段树等位结点编号*/, int p, int v)//建立下一棵线段树,相当于线段树的单点更新,只需保存一条链而已
{
	ln[p] = ln[last]; rn[p] = rn[last];//这棵线段树和上一棵一样,直接赋值
	value[p] = value[last] + 1;//明显v包含在区间里,直接加一即可
	if (ln[p] == rn[p]) return;//叶节点,不用继续更新,直接返回即可
	if (v <= (ln[p] + rn[p] >> 1))//包含在左儿子的区间中
	{
		rs[p] = rs[last];//右子树(即右儿子)和上一棵线段树的一样
		ls[p] = ++cnt;//累计节点编号
		//本来更新节点的值是写在这里的,但这样根节点就更新不了了,于是写到了前面
		updata(ls[last], ls[p], v);//建立左子树
	}
	else//反之亦然同理
	{
		ls[p] = ls[last];
		rs[p] = ++cnt;
		updata(rs[last], rs[p], v);
	}
}
void build()//建立主席树
{
	root[0] = cnt;//0号根节点为空树,便于相减
	bud(0, n2 - 1, cnt);//先建一发空树
	for (int i = 0; i < n; i++)//[0,n)和(0,n]皆可,只不过是root[i-1]和root[i+1]的区别
	{
		root[i + 1] = ++cnt;//累计根节点
		updata(root[i], root[i + 1], num[i]);//更新这棵线段树
	}
}
//这类宏定义一定要加括号，否则死的很惨！！！！！！
//我才不会告诉你我就是因为这个第一次交爆零了...
//还有,宏定义这种东西作用范围是当前文件...写在哪里都一样...
#define lv (value[ls[r]]-value[ls[l]])//相减后得到的线段树左儿子的值
#define rv (value[rs[r]]-value[rs[l]])//相减后得到的线段树右儿子的值
int ans;//落谷猥琐巨坑,直接返回会MLE!!!被迫改void并使用全局变量保存答案
void query(int k, int l, int r)//这里的l和r指的不是数列的区间,而是l棵线段树和第r棵线段树的根节点
{
	//直接写成(其实就是)权值的查询就好
	if (ln[l] == rn[l])//叶节点,直接记录答案
	{
		ans = ln[l];
		return;
	}
	if (k <= lv)//左儿子包含的数的个数大于等于待查询的k
		query(k, ls[l], ls[r]);//向左儿子查询第k小即可
	else//左儿子包含的数的个数小于待查询的k
		query(k - lv, rs[l], rs[r]);//整段区间的第k小即为右区间的第(k-左区间包含数的个数)小
}
map <int, int> po/*由原值映射到离散化后的值*/, re/*由离散化后的值映射到原值*/;
int main()
{
	cin >> n;//输入,显然
	int m;
	cin >> m;
	for (int i = 0; i < n; i++)//输入并保存副本用于离散化
	{
		cin >> num[i];
		tmp[i] = num[i];
	}
	//---------------------------------------离散化--------------------------------------------
	sort(tmp, tmp + n);//先来一发排序
	//巨坑!!tmp+n是排序区间末区间端点的下一个值的地址!!!
	//我也不知道STL为什么要这样反正我就这样爆了两个点
	n2 = unique(tmp, tmp + n) - tmp;//去重也一样!!!(STL的东西都是这个尿性)
	for (int i = 0; i < n2; i++)//记录离散化后的数值
	{
		po[tmp[i]] = i;
		re[i] = tmp[i];
	}
	for (int i = 0; i < n; i++)//将原值变为离散化后的值
	{
		num[i] = po[num[i]];
	}
	//-----------------------------------------------------------------------------------------
	build();//建立主席树
	int l, r, k;
	while (m--)
	{
		cin >> l >> r >> k;
		l--;
		query(k, root[l], root[r]);//一定要传递根节点的编号!!!!!!
		cout << re[ans] << '\n';//输出答案,一定要离散化的数值搞回来!!!小心爆零!!!
	}
	return 0;
}
```