如题，这是一个模板。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 inline void read(int & x) 9 {10 x = 0;11 int k = 1;12 char c = getchar();13 while (!isdigit(c))14 if (c == '-') c = getchar(), k = -1;15 else c = getchar();16 while (isdigit(c))17 x = (x << 1) + (x << 3) + (c ^ 48),18 c = getchar();19 x *= k;20 }21 22 const int MAXN = 202020;23 24 struct sgt25 {26 int l, r, w;27 }t[MAXN << 5];28 29 int n, m, id = 0, cnt = 0, L, R, K;30 int root[MAXN], a[MAXN], b[MAXN];31 32 inline int Lsh(int x) { return std::lower_bound(a + 1, a + cnt + 1, x) - a; }33 34 void Pushup(int u)35 {36 t[u].w = t[t[u].l].w + t[t[u].r].w;37 }38 39 void Build(int u, int l, int r)40 {41 if (l == r)42 {43 t[u].l = -1;44 t[u].r = -1;45 t[u].w = 0;46 return;47 }48 t[u].l = ++id;49 t[u].r = ++id;50 int mid = (l + r) >> 1;51 Build(t[u].l, l, mid);52 Build(t[u].r, mid + 1, r);53 Pushup(u);54 }55 56 int Add(int u, int l, int r, int k)57 {58 int cur = ++id;59 t[cur].l = t[u].l;60 t[cur].r = t[u].r;61 t[cur].w = t[u].w + 1;62 if (l < r)63 {64 int mid = (l + r) >> 1;65 if (k <= mid) t[cur].l = Add(t[u].l, l, mid, k);66 else t[cur].r = Add(t[u].r, mid + 1, r, k);67 }68 return cur;69 }70 71 int Query(int u, int v, int l, int r, int k)72 {73 if (l == r) return l;74 int df = t[t[v].l].w - t[t[u].l].w;75 int mid = (l + r) >> 1;76 if (df < k) return Query(t[u].r, t[v].r, mid + 1, r, k - df);77 else return Query(t[u].l, t[v].l, l, mid, k);78 }79 80 signed main()81 {82 read(n), read(m);83 for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];84 std::sort(a + 1, a + n + 1);85 cnt = std::unique(a + 1, a + n + 1) - a - 1;86 Build(root[0] = ++id, 1, cnt);87 for (int i = 1; i <= n; ++i)88 root[i] = Add(root[i - 1], 1, cnt, Lsh(b[i]));89 for (int i = 1; i <= m; ++i)90 {91 read(L), read(R), read(K);92 int p = Query(root[L - 1], root[R], 1, cnt, K);93 printf("%d\n", a[p]);94 }95 return 0;96 }
