12/24
09:26
Description
给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。
Input
第一行两个数n，m。 第二行n个数，a[i]。 接下来m行，每行两个数l,r，表示询问[l,r]这个区间。
Output
m行，每行对应一个答案。
Sample Input
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
1
0
3
0
4
HINT
【数据范围】
n,m≤500000
2016.7.9重设空间，但未重测！
Source
By Dzy
主席树。
|
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 |
#include <iostream> #include <cstdio> using namespace std; const int SZ = 1e6 + 10; struct SGT { int l, r, cnt; }tree[SZ * 10]; int rt[SZ], Tcnt; void read(int &num) { num = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();} while('0' <= c && c <= '9'){num = num * 10 + (c - '0'); c = getchar();} num *= f; } void insert(int l, int r, int x, int &y, int v) { y= ++Tcnt; tree[y] = tree[x]; tree[y].cnt++; if(l == r) return ; int mid = (l + r) >> 1; if(v <= mid) insert(l, mid, tree[x].l, tree[y].l, v); else insert(mid + 1, r, tree[x].r, tree[y].r, v); } int ask(int l, int r, int x, int y, int k) { while(l != r) { if(tree[y].cnt - tree[x].cnt <= k) return 0; int mid = (l + r) >> 1; if(tree[tree[y].l].cnt - tree[tree[x].l].cnt > k) { x = tree[x].l; y = tree[y].l; r = mid; } else if(tree[tree[y].r].cnt - tree[tree[x].r].cnt > k) { x = tree[x].r; y = tree[y].r; l = mid + 1; } else return 0; } return l; } int main() { int n, m; read(n), read(m); int value; for(int i = 1; i <= n; i++) { read(value); insert(1, n, rt[i - 1], rt[i], value); } int l, r; while(m--) { read(l), read(r); printf("%d\n", ask(1, n, rt[l - 1], rt[r], (r - l + 1) / 2)); } return 0; } |