题目大意
给出一个序列，，问一段区间内有没有出现过一半以上的数字。
思路
用主席树取区间出来，在权值线段树上找。
CODE;struct SegTree{SegTree *son[2];int cnt;}mempool[MAXR], *C = mempool, *root[MAX];SegTree *NewSegTree(SegTree *_, SegTree *__, int ___){C->son[0] = _;C->son[1] = __;C->cnt = ___;return C++;}SegTree *Insert(SegTree *consult, int l, int r, int x){if(l == r)return NewSegTree(consult->son[0], consult->son[1], consult->cnt + 1);int mid = (l + r) >> 1;if(x <= mid)return NewSegTree(Insert(consult->son[0], l, mid, x), consult->son[1], consult->cnt + 1);elsereturn NewSegTree(consult->son[0], Insert(consult->son[1], mid + 1, r, x), consult->cnt + 1);}int Ask(SegTree *left, SegTree *right, int l, int r, int c){if(l == r) return l;int mid = (l + r) >> 1;if(right->son[0]->cnt – left->son[0]->cnt > c)return Ask(left->son[0], right->son[0], l, mid, c);else if(right->son[1]->cnt – left->son[1]->cnt > c)return Ask(left->son[1], right->son[1], mid + 1, r, c);return 0;}int cnt, asks;int main(){root[0] = NewSegTree(C, C, 0);cin >> cnt >> asks;for(int x, i = 1; i <= cnt; ++i) {scanf(“%d”, &x);root[i] = Insert(root[i – 1], 1, cnt, x);}for(int x, y, i = 1; i <= asks; ++i) {scanf(“%d%d”, &x, &y);printf(“%d\n”, Ask(root[x – 1], root[y], 1, cnt, (y – x + 1) / 2));}return 0;}
对于旅行，从来都记忆模糊。记不得都去了哪些地方，
