这是个非常经典的主席树入门题——静态区间第 kk 小。

数据已经过加强，请使用主席树。同时请注意常数优化。

如题，给定 nn 个整数构成的序列 aa，将对于指定的闭区间 [l, r][l,r] 查询其区间内的第 kk 小值。

第一行包含两个整数，分别表示序列的长度 nn 和查询的个数 mm。
第二行包含 nn 个整数，第 ii 个整数表示序列的第 ii 个元素 a_iai?。
接下来 mm 行每行包含三个整数 l, r, kl,r,k , 表示查询区间 [l, r][l,r] 内的第 kk 小值。

对于每次询问，输出一行一个整数表示答案。

样例 1 解释

n=5n=5，数列长度为 55，数列从第一项开始依次为\{25957, 6405, 15770, 26287, 26465\}{25957,6405,15770,26287,26465}。

• 第一次查询为 [2, 2][2,2] 区间内的第一小值，即为 64056405。
• 第二次查询为 [3, 4][3,4] 区间内的第一小值，即为 1577015770。
• 第三次查询为 [4, 5][4,5] 区间内的第一小值，即为 2628726287。
• 第四次查询为 [1, 2][1,2] 区间内的第二小值，即为 2595725957。
• 第五次查询为 [4, 4][4,4] 区间内的第一小值，即为 2628726287。

数据规模与约定

• 对于 20\%20% 的数据，满足 1 \leq n,m \leq 101≤n,m≤10。
• 对于 50\%50% 的数据，满足 1 \leq n,m \leq 10^31≤n,m≤103。
• 对于 80\%80% 的数据，满足 1 \leq n,m \leq 10^51≤n,m≤105。
• 对于 100\%100% 的数据，满足 1 \leq n,m \leq 2\times 10^51≤n,m≤2×105

• #include<iostream>
  #include<algorithm>
  using namespace std;
  struct asd
  {
      long long ls,rs;
      long long cnt;
  } tr[4000001];
  long long n,m,a[4000001],tot=0,root[4000001],b[4000001];
  long long build(long long l,long long r)
  {
      long long rt=++tot;
      long long mid=(l+r)/2;
      if(l!=r)
      {
          tr[rt].ls=build(l,mid);
          tr[rt].rs=build(mid+1,r);
      }
      return rt;
  }
  long long change(long long x,long long l,long long r,long long p)
  {
      long long rt=++tot;
      tr[rt]=tr[p];
      tr[rt].cnt=tr[p].cnt+1;
      if(l==r) 
          return rt;
      long long mid=(l+r)/2;
      if(x<=mid)
          tr[rt].ls=change(x,l,mid,tr[p].ls);
      else
          tr[rt].rs=change(x,mid+1,r,tr[p].rs);
      return rt;
  }
  long long ask(long long p,long long q,long long l,long long r,long long k)
  {
      if(l==r) return l;
      long long mid=(l+r)/2;
      long long lcnt=tr[tr[q].ls].cnt-tr[tr[p].ls].cnt;
      if(k<=lcnt) return ask(tr[p].ls,tr[q].ls,l,mid,k);
      else return ask(tr[p].rs,tr[q].rs,mid+1,r,k-lcnt);
  }
  int main()
  {
      cin>>n>>m;
      for(long long i=1;i<=n;i++)
      {
          cin>>a[i];
          b[i]=a[i];
      }
      sort(b+1,b+1+n);
      long long q=unique(b+1,b+1+n)-b-1;
      root[0]=build(1,q);
      for(long long i=1;i<=n;i++)
      {
          long long t=lower_bound(b+1,b+1+q,a[i])-b;
          root[i]=change(t,1,q,root[i-1]);
      }
      long long l,r,k;
      for(long long i=1;i<=m;i++)
      {
          cin>>l>>r>>k;
          cout<<b[ask(root[l-1],root[r],1,q,k)]<<endl;
      }
      return 0;
  }