CF840D：Destiny（线段树）

D. Destiny time limit per test 2.5 seconds memory limit per test 512 megabytes input standard input output standard output

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  times or  - 1 if there is no such number. Help Leha with such a difficult task.

Input

First line of input data contains two integers n and q (1 ≤ n, q ≤ 3·105) — number of elements in the array and number of queries respectively.

Next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — Leha's array.

Each of next q lines contains three integers l, r and k (1 ≤ l ≤ r ≤ n, 2 ≤ k ≤ 5) — description of the queries.

Output

Output answer for each query in new line.

Examples input 4 2 1 1 2 2 1 3 2 1 4 2 output 1 -1 input 5 3 1 2 1 3 2 2 5 3 1 2 3 5 5 2 output 2 1 2

题意：给N个数·，Q个询问，每个询问找出区间内出现次数大于所给公式的值中最小的那一个。

思路：

①线段树，每个点都建一棵新的线段树，查询时优先处理左子树，比较一下两个点之间新增的节点数是否满足题意即可。

# include <bits/stdc++.h> using namespace std; const int maxn = 3e5+3; const int maxnn = 1e7+3; struct node{int l, r, v;}nd[maxnn]; int n, q, t, id, root[maxn]; inline void scan(int &ret) { char c; ret=0; while((c=getchar())<'0'||c>'9'); while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar(); } int update(int pre, int l ,int r, int val) { int cur = ++id; nd[cur] = nd[pre]; ++nd[cur].v; if(l == r) return cur; int m = l+r>>1; if(val > m) nd[cur].r = update(nd[pre].r, m+1, r, val); else nd[cur].l = update(nd[pre].l, l, m, val); return cur; } int query(int x, int y, int l, int r, int val) { if(nd[x].v-nd[y].v <= val) return -1; if(l == r) return l; int m = l+r>>1, ans; ans = query(nd[x].l, nd[y].l, l, m, val); if(ans == -1) ans = query(nd[x].r, nd[y].r, m+1, r, val); return ans; } int main() { int l, r, k; scan(n), scan(q); for(int i=1; i<=n; ++i) scan(t=0), root[i] = update(root[i-1], 1, n, t); while(q--) { scan(l), scan(r), scan(k); printf("%d\n",query(root[r], root[l-1], 1, n, (r-l+1)/k)); } return 0; } ②莫队算法，普通莫队要O(n^1.5 * lgn)超时了，正解是限定块长度len=sqrt(5n)，将出现次数>=len/5预先存起来，然后再莫队，如果询问 区间大于len，就从预存的数里面遍历，因为此时如果有解，该数的出现次数一定>=len/5次。

TLE版本：

# include <bits/stdc++.h> # define mp make_pair using namespace std; const int maxn = 3e5+30; int len, a[maxn], num[maxn]; int ans[maxn]; set<pair<int,int> >s; struct node { int l, r, id, k, block; node(){} node(int l, int r, int k, int id):l(l), r(r), k(k), id(id){block = l/len;} bool operator <(const node b)const { if(block == b.block) return r <b.r; return block < b.block; } }q[maxn]; int main() { int n, Q; scanf("%d%d",&n,&Q); len = sqrt(n); for(int i=0; i<n; ++i) scanf("%d",&a[i]); for(int i=0; i<Q; ++i) { int l, r, k; scanf("%d%d%d",&l,&r,&k); --l,--r; q[i] = node(l,r,k,i); } sort(q, q+Q); int l=0, r=0; ++num[a[0]]; s.insert(mp(1, a[0])); for(int i=0; i<Q; ++i) { node &t = q[i]; while(r < t.r) { ++num[a[++r]]; s.insert(mp(num[a[r]], a[r])); } while(l > t.l) { ++num[a[--l]]; s.insert(mp(num[a[l]], a[l])); } while(r > t.r) { s.erase(s.find(mp(num[a[r]], a[r]))); --num[a[r--]]; } while(l < t.l) { s.erase(s.find(mp(num[a[l]], a[l]))); --num[a[l++]]; } int tmp = (t.r-t.l+1)/t.k+1; auto p = s.lower_bound(mp(tmp, 0)); if(p == s.end()) ans[t.id] = -1; else ans[t.id] = p->second; } for(int i=0; i<Q; ++i) printf("%d\n",ans[i]); return 0; }