今天學習了一下主席樹（名字這么強的嘛）
雖然直接理解起來不容易，但是這種解決問題的思想其實并不陌生。
我們可以首先來看維護整個區間第K大的線段樹
我們將[l,r]區間內數字的多少用線段樹進行維護，這樣的話為了求取區間第k大，我們先看左區間有多少個數字，如果左區間就有多于K的數字（或者等于K個），我們直接去左區間找，如果左區間沒有K個，我們就去右區間找，找右區間第K-左區間數字個數大的數

void query(int k,int l,int r,int k)
{if(l==r) return l;int mid=(l+r)>>1;if(tree[k<<1].num>=k) query(k<<1,l,mid,k);else query(k<<1|1,mid+1,r,k);
}

但是我們要求解的問題沒有這么簡單，我們需要很方便的求任意區間第K大，比較容易想到的方法是給每個區間建立一個線段樹，然后找哪個查哪個，然而這樣的時空復雜度顯然是不允許的。
我們可以來看另一個問題，就是我們想要很方便地查詢任意區間和，我們的第一想法是不是也是將任意區間和計算出來然后輸出呢？同樣不允許的情況下，我們引入了前綴和，計算從[1…i]的和，然后[l,r]的和就是sum[r]-sum[l-1]
同樣的，對于我們想要很方便的求取區間第K大問題，我們也引入前綴和的思想，我們保存從1…n的所有維護[1…i]區間內任意區間數字個數的線段樹（就像上面那樣），然后想要求解的是[l,r]，那么[l,r]區間內任意區間數字個數就是tree[ root[r] ].num-tree[ root[l-1] ].num，然后就能像上面一樣求解問題啦
然而，我們需要保存1…n所有維護[1…i]區間內任意區間數字個數的線段樹，也是很不容易做到的，但是在每一次更新的時候（多加入一個數字），我們只會修改從這個數字到根節點的不超過logn個節點，其他的節點都是相同的，那么我們不妨就直接用沒有改變的節點，再重新申請需要修改的節點。因為一個兒子可能被多個父親使用，所以這個時候的父親和兒子節點已經不滿足2n和2n+1的關系，我們就需要每個節點保存他的左兒子和右兒子的指針，這里我們用數組下標模擬指針，同時，我們還需要一個root數組保存每個線段樹的根節點的指針
對于區間[1…i]的線段樹，他的根節點一開始是和前面一個元素的根節點是相同的，左兒子和右兒子以及區間數字的個數也是相同的，然后我們加入一個新元素a[i]，如果a[i]在左區間就建立一個新的左兒子節點，這個左兒子一開始也和之前的左兒子相同，我們再更新這個左兒子，直到更新到葉子節點，右兒子同理
代碼如下

struct node
{int l,r,cnt;
}tree[MAXN];void insert(int &x,int num,int l,int r)
{tree[++t]=tree[x]; tree[t].cnt++; x=t;	//t指向當前可分配空間的數組的下標（相當于新節點的指針）if(l==r) return;int mid=(l+r)>>1;if(num<=mid) insert(tree[x].l,num,l,mid);else insert(tree[x].r,num,mid+1,r);
}

查詢的話和最上面的代碼類似

int query(int i,int j,int k,int l,int r)
{if(l==r) return l;int tmp=tree[tree[j].l].cnt-tree[tree[i].l].cnt;//左區間的元素個數int mid=(l+r)>>1;if(k<=tmp){return query(tree[i].l,tree[j].l,k,l,mid);}else{return query(tree[i].r,tree[j].r,k-tmp,mid+1,r);}
}

因為我們需要維護數據范圍大小的區間，這可能是做不到的，[-1e-9~1e9]都做不到。因此我們需要進行離散化
離散化代碼：

scanf("%d%d",&N,&M);for(int i=1;i<=N;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+N+1);	//排序n=unique(b+1,b+1+N)-b-1;//去重后指向不包含重復元素的末尾的后一個元素（后面都是與前面重復的），n就是不重復元素的個數t=0;for(int i=1;i<=N;i++){a[i]=lower_bound(b+1,b+1+n,a[i])-b;	//a[i]重新賦值為在b[i]的次序，離散化}

完整代碼：（哦，對了，還要注意開空間，在網上聽大佬說得開n*40的空間，巨恐怖）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<climits>using namespace std;const int MAXN=2000010;
int a[MAXN],b[MAXN],root[MAXN];
int N,M,n,t;
struct node
{int l,r,cnt;
}tree[MAXN];void insert(int &x,int num,int l,int r)
{tree[++t]=tree[x]; tree[t].cnt++; x=t;if(l==r) return;int mid=(l+r)>>1;if(num<=mid) insert(tree[x].l,num,l,mid);else insert(tree[x].r,num,mid+1,r);
}int query(int i,int j,int k,int l,int r)
{if(l==r) return l;int tmp=tree[tree[j].l].cnt-tree[tree[i].l].cnt;int mid=(l+r)>>1;if(k<=tmp){return query(tree[i].l,tree[j].l,k,l,mid);}else{return query(tree[i].r,tree[j].r,k-tmp,mid+1,r);}
}int main()
{int T,u,v,k;scanf("%d",&T);while(T--){scanf("%d%d",&N,&M);for(int i=1;i<=N;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+N+1);n=unique(b+1,b+1+N)-b-1;t=0;for(int i=1;i<=N;i++){a[i]=lower_bound(b+1,b+1+n,a[i])-b;}root[0]=tree[0].l=tree[0].r=tree[0].cnt=0;for(int i=1;i<=N;i++){root[i]=root[i-1];insert(root[i],a[i],1,n);}for(int i=0;i<M;i++){scanf("%d%d%d",&u,&v,&k);printf("%d\n",b[query(root[u-1],root[v],k,1,n)]);}}return 0;
}