题目描述
Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.
题意概述
给定包含$n$个数的序列,有$q$次询问,每次询问给定$l, r, k$,求区间$[l, r]$中出现次数严格大于${r-l+1 \over k}$的最小数字。
数据范围:$1 \le n, q \le 3 \times 10^5, \; 1 \le a_i \le n, \; 2 \le k \le 5$。
算法分析
建主席树,第$i$个位置上的线段树是前$i$个数的权值线段树。这样就可以用前缀和思想快速求出区间$[l, r]$中某个数出现的次数。对于每个询问,用第$r$个位置上线段树的值减去第$(l-1)$个位置上线段树的值,直接在主席树上暴力查找。由于$k$比较小,查找复杂度不会太高。
代码
#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; }