可怜的狗狗(Poor Doggie)

小卡家有 $n$ 只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第 $i$ 只到第 $j$ 只狗中第 $k$ 漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间 $[i,j]$ 不互相包含。

第一行输入两个数 $n,m$ ， $m$ 表示嘉嘉喂食的次数

第二行 $n$ 个整数，表示第 $i$ 只狗的漂亮值为 $a_i$ 。

接下来 $m$ 行，每行 $3$ 个整数 $i,j,k$ ，表示询问这次喂食喂第 $i$ 到第 $j$ 只狗中第 $k$ 漂亮的狗的漂亮值。

$m$ 行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

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

3
2

$1\le n \le 3\times 10^5 ,1\le m \le5\times10^4,0\le a_i<2^{31}$，且 $a_i$ 互不相同。

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~7	小规模 n≤2000,m≤1000 / 边界 n=m=1 / k=1与k=区间长度极值
2	15	8~11	Hack: 权值覆盖 0 ~ 2^31-1 / Hack: 窗口每步右移1格的长窗口滑动 / 逆序输入的不包含区间
3	30	12~20	满规模 n=3×10^5, m=5×10^4 区间第k小查询压力
4	25	21~25	随机互不包含区间集合回归测试

出处：原题链接

#P1533. 可怜的狗狗(Poor Doggie)