1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
| #include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>
using namespace std;
struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline IOManager r(T &x) { read(x); return *this; } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char c) { putchar(c); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } template <typename T> inline IOManager w(T x) { write(x); return *this; } } io;
struct SegmentTree { private: static const int N = 9000000; int tot; struct Node { int val, child[2]; } node[N]; int add_point(int root, int l, int r, int p) { if (l == r) { node[++ tot] = (Node) { node[root].val, 0, 0 }; ++ node[tot].val; return tot; } int mid = l + r >> 1, rec = ++ tot; node[rec] = (Node) { 0, 0, 0 }; if (p <= mid) { node[rec].child[1] = node[root].child[1]; node[rec].child[0] = add_point(node[root].child[0], l, mid, p); } else { node[rec].child[0] = node[root].child[0]; node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p); } node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val; return rec; } int query_point(int root1, int root2, int l, int r, int p) { if (node[root2].val - node[root1].val < p) return -1; if (l == r) return node[root2].val - node[root1].val >= p ? l : -1; int mid = l + r >> 1, res = -1; if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p) res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p); if (~ res) return res; res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p); return res; }
public: int n, cnt, root[N]; void add(int p) { root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt; } int find(int l, int r, int p) { return query_point(root[l - 1], root[r], 1, n, p); } void print() { cout << cnt << endl; for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' '; cout << endl << tot << endl; for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl; } };
struct Solver { private: int n, q; SegmentTree tree; void input() { io.r(n).r(q); tree.n = n; for (int i = 1; i <= n; ++ i) { int t; io.read(t), tree.add(t); } } void process() { int l, r, k; io.r(l).r(r).r(k); int p = (r - l + 1) / k + 1; io.w(tree.find(l, r, p)).w('\n'); }
public: void solve() { input(); while (q --) process(); } } solver;
int main() { solver.solve(); return 0; }
|