想问下dalao是不是这题用指针很危险。

#include <bits/stdc++.h>
#define MAX_N 200000 + 10
#define INF 1 << 31 - 1
typedef long long ll;
using namespace std;
struct numm {
  ll x;
  int id;
}num[MAX_N];

struct node {
  int tms;
  node* ch[2];
};
node* null;
node* root[MAX_N];

int N, M;
ll x[MAX_N], x2[MAX_N];
map<int, int> mp;

bool cmp (const numm a, const numm b) {return a.x < b.x;}
void turn () {
  sort (num + 1, num + N + 1, cmp);
  int top = 2;
  ll now = num[1].x, now2;
  num[1].x = 1;
  for (int i = 2;i <= N; ++i) {
    now2 = num[i].x;
    num[i].x = now2 == now ? top - 1 : top++;
    now = now2;
  }
  for (int i = 1;i <= N; ++i) {
    x[num[i].id] = num[i].x;
  }
}

void init (node* &o, int l, int r, int x) {
  //printf("%d %d\n", l, r);
  o = new node();
  o -> ch[0] = o -> ch[1] = null;
  if (l <= x && r >= x) o -> tms++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  init (o -> ch[0], l, mid, x);
  init (o -> ch[1], mid + 1, r, x);
}

int check (int l, int r, int mid, int x) {
  if (l <= x && x <= mid) return 0;
  return 1;
}

void build (node* &o, int l, int r, int x, node* s) {
  //printf("%d %d %d\n", l, r, s -> tms + 1);
  o = new node();
  o -> tms = s -> tms + 1;
  o -> ch[0] = o -> ch[1] = null;
  int mid = (l + r) >> 1;
  if (l == r) return;
  int d = check(l, r, mid, x);
  o -> ch[d ^ 1] = s -> ch[d ^ 1];
  if (d == 0) build (o -> ch[d], l, mid, x, s -> ch[d]);
  else build (o -> ch[d], mid + 1, r, x, s -> ch[d]);
}

int kth (node* o1, node* o2, int l, int r, int k) {
  //printf("%d %d %d   %d %d\n", l, r, k, o1 -> tms, o2 -> tms);
  int x = o2 -> ch[0] -> tms - o1 -> ch[0] -> tms;
  if (l == r) return l;
  int d = k <= x ? 0 : 1;
  int mid = (l + r) >> 1;
  // printf("%d\n", mid);
  if (d == 0) return kth(o1 -> ch[d], o2 -> ch[d], l, mid, k);
  else return kth(o1 -> ch[d], o2 -> ch[d], mid + 1, r, k - x);
}

void init_root () {for (int i = 1;i <= N; ++i) root[i] = null;}
void init_null () {null = new node(); null -> tms = 0;}
int main () {
  init_null();
  init_root();
  scanf("%d%d", &N, &M);
  for (int i = 1;i <= N; ++i) {
    scanf("%lld", &num[i].x);x2[i] = num[i].x;
    num[i].id = i;
  }
  turn();
  //for (int i = 1;i <= N; ++i) printf("%d ", x[i]); printf("\n");
  for (int i = 1;i <= N; ++i) mp[x[i]] = x2[i];
  //for (int i = 1;i <= N; ++i) printf("%d ", mp[x[i]]); printf("\n");

  init(root[0], 1, N, 0);
  init(root[1], 1, N, x[1]);

  for (int i = 2;i <= N; ++i) 
    build (root[i], 1, N, x[i], root[i - 1]);
  
  int l, r, k, res;
  for (int i = 1;i <= M; ++i) {
    scanf("%d%d%d", &l, &r, &k);
    //printf("%d %d %d\n", l, r, k);
    res = kth(root[l - 1], root[r], 1, N, k);
    printf("%d\n", mp[res]);
  }
  return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int n,m;
int a[500100],b[500100];
map<int,int>num;
struct node{
    int l,r,sum;
}tree[12000100];
int root[500100];
int tot;
void update(int k1,int k2,int l,int r,int x)//k1-build,k2-find
{
    if(l==r)
    {
        tree[k1].sum=tree[k2].sum+1;
        return;
    }
    else
    {
        int mid=(l+r)/2;
        if(x>=l&&x<=mid)
        {
            tot++;
            tree[k1].l=tot;
            tree[k1].r=tree[k2].r;
            update(tree[k1].l,tree[k2].l,l,mid,x);

        }
        else
        {
            tot++;
            tree[k1].r=tot;
            tree[k1].l=tree[k2].l;
            update(tree[k1].r,tree[k2].r,mid+1,r,x);
        }
    }
    tree[k1].sum=tree[tree[k1].l].sum+tree[tree[k1].r].sum;
}
int query(int i,int j,int k,int l,int r)
{
    if(l==r)  return l;
    int t=tree[tree[j].l].sum-tree[tree[i].l].sum;
    int mid=(l+r)/2;
    if(k<=t)  return query(tree[i].l,tree[j].l,k,l,mid);
    else      return query(tree[i].r,tree[j].r,k-t,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)  b[i]=a[i];
    sort(b+1,b+n+1);
    int o=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=o;i++)    num[b[i]]=i;
    for(int i=1;i<=n;i++)    root[i]=i;
    tot=n;
    for(int i=1;i<=n;i++)    update(i,i-1,1,o,num[a[i]]);
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        printf("%d\n",b[query(root[u-1],root[v],c,1,o)]);
    }
    return 0;
}