day1

代码：

struct Matrix {
  int a[3][3];
  Matrix & operator * (const Matrix & rhs) {
  }
}a[MAXN];
struct Node { // [l, r]
  Matrix mat;
  Node *ls, *rs;
  void pushup() {
    mat = ls->mat * rs->mat;
  }
};
Node *build(int l, int r) {
  Node *cur = newNode();
  if(l < r) {
    int mid = (l + r) / 2;
    cur->ls = build(l, mid);
    cur->rs = build(mid + 1, r);
    cur->pushup();
  } else {
    cur->mat = a[l];
  }
  return cur;
}
void modify(Node *cur, int l, int r, int p, Matrix v) {
  if(l == r) {
    cur->mat = v;
  } else {
    int mid = (l + r) / 2;
    if(p <= mid) modify(cur->ls, l, mid, p, v);
    else modify(cur->rs, mid + 1, r, p, v);
    cur->pushup();
  }
}
void modify(int cur, int l, int r, int p, Matrix v) {
  if(l == r) {
    st[cur] = v;
  } else {
    int mid = (l + r) / 2;
    if(p <= mid) modify(cur << 1, l, mid, p, v);
    else modify(cur << 1 | 1, mid + 1, r, p, v);
    pushup(cur);
  }
}
Matrix st[MAXN<<2], a[MAXN];
void pushup(int cur) {
  st[cur] = st[cur << 1] * st[cur << 1 | 1];
}
void build(int cur, int l, int r) {
  if(l < r) {
    int mid = (l + r) / 2;
    build(cur << 1, l, mid);
    build(cur << 1 | 1, mid + 1, r);
    pushup(cur);
  } else {
    st[cur] = a[l];
  }
}
bool tag[MAXN<<2];
void pushdown(int cur) {
  if(tag[cur]) {
    swapRow(st[cur]);
    tag[cur << 1] ^= 1;
    tag[cur << 1 | 1] ^= 1;
    tag[cur] = 0;
  }
}
Node *newNode() {
  static int cnt = 0;
  return &pool[cnt++];
}
int cnt = 0;
Node *newNode() {
  return &pool[cnt++];
}
bool lxl_is_hentai[233];
0000 0000
0000 0001
bitset<32> lxl_is_hentai;
lxl_is_hentai.count();
unsigned int tmp = 0;
0000 0000 0000 0000 0000 0000 0000 0000
bool a[233], b[233];
for(int i = 0; i < 233; i++) {
  a[i] |= b[i];
}
O(233)
for(int i = 0; i < 256 / 32, i++) {
  tmp[i] |= ...;
} 
O(n / 32)
struct Node {
  bitset<2018> bit;
  Node *ls, *rs;
}x;
void set(Node *cur, int v) {
  cur->bit.reset();
  cur->bit[v] = 1;
}
3 2
6 4
9 3
11 9
int st[MAXN];
void add(int x) {
  st[rank[x]]++;
}
set<int> S;
int find(set<int> & S, int x) { // 第一个大于等于 x 的数
  set<int>::iterator it = S.lower_bound(x);
  if(it == S.end()) return -1;
  return *it;
}
struct OPT {
  int type, val, t;
};
vector<OPT> vec[MAXN];
void add(int l, int r, int k) { // [l, r] 加 k
  vec[l].push_back(OPT{1, k, curTime});
  vec[r + 1].push_back(OPT{1, -k, curTime});
}
void query(int p) { // 查询 p 的历史最大值
  vec[p].push_back(OPT{2, -1, curTime});
}
void work() {
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < vec[i].size(); j++) {
      OPT cur = vec[i][j];
      if(cur.type == 1) {
        seg.add(1, cur.curTime, cur.k);
      }
    }
    for(int j = 0; j < vec[i].size(); j++) {
      OPT cur = vec[i][j];
      if(cur.type == 2) {
        ans = seg.queryMax(1, cur.curTime);
      }
    }
  }
}
void insert(Node *pre, Node *&cur, int l, int r, int p, int v) {
  cur = newNode(); *cur = *pre;
  if(l == r) {
    cur->val += v;
  } else {
    int mid = (l + r) / 2;
    if(p <= mid) insert(pre->ls, cur->ls, l, mid, p, v);
    else insert(pre->rs, cur->rs, mid + 1, r, p, v);
  }
}
void init() {
  root[0] = build(1, n);
  for(int i = 1; i <= n; i++) {
    insert(root[i - 1], root[i], 1, n, a[i], 1);
  }
}
int query(Node *pre, Node *cur, int l, int r, int k) {
  int res;
  if(l == r) {
    res = l;
  } else {
    int left = cur->ls->val - pre->ls->val;
    int mid = (l + r) / 2;
    if(left >= k) {
      res = query(pre->ls, cur->ls, l, mid, k);
    } else {
      res = query(pre->rs, cur->rs, mid + 1, r, k - left);
    }
  }
  return res;
}
int work(int l, int r, int k) {
  return query(root[l - 1], root[r], 1, n, k);
}

//luogu P3834
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
int a[MAXN], b[MAXN], c[MAXN];
struct Node {
  int val;
  Node *ls, *rs;
  Node(): val(0), ls(NULL), rs(NULL) { }
}pool[MAXN*20], *root[MAXN];
Node *newNode() {
  static int cnt = 0;
  return &pool[cnt++];
}
Node *build(int l, int r) {
  Node *cur = newNode();
  if(l < r) {
    int mid = (l + r) / 2;
    cur->ls = build(l, mid);
    cur->rs = build(mid + 1, r);
  }
  return cur;
}
void insert(Node *pre, Node *&cur, int l, int r, int p) {
  cur = newNode(); *cur = *pre; cur->val++;
  if(l < r) {
    int mid = (l + r) / 2;
    if(p <= mid) insert(pre->ls, cur->ls, l, mid, p);
    else insert(pre->rs, cur->rs, mid + 1, r, p);
  }
}
int query(Node *rt1, Node *rt2, int l, int r, int k) {
  int res = -1;
  if(l == r) {
    res = c[l];
  } else {
    int mid = (l + r) / 2;
    int left = rt2->ls->val - rt1->ls->val;
    if(left >= k) {
      res = query(rt1->ls, rt2->ls, l, mid, k);
    } else {
      res = query(rt1->rs, rt2->rs, mid + 1, r, k - left);
    }
  }
  return res;
}
int main() {
  int n, m;
  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);
  int tot = unique(b + 1, b + n + 1) - b - 1;
  for(int i = 1; i <= n; i++) {
    int p = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    c[p] = a[i], a[i] = p;
  }
  root[0] = build(1, tot);
  for(int i = 1; i <= n; i++) {
    insert(root[i - 1], root[i], 1, tot, a[i]);
  }
  while(m--) {
    int l, r, k;
    scanf("%d %d %d", &l, &r, &k);
    printf("%d\n", query(root[l - 1], root[r], 1, tot, k));
  }
  return 0;
}