POI 21th Couriers

http://main.edu.pl/en/archive/oi/21/kur

題目：區間查詢有沒有數字的量嚴格大於一半，假如有就輸出，沒有則輸出0

一直覺得很神奇XD 首先抓出候選人，然後真的去確認他的數量


#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>

using namespace std;

struct node{int id, hp; node(int _id = 0, int _hp = 0):id(_id),hp(_hp){return;}};

node operator+(const node& a, const node& b){
    node ret;
    if(a.id == b.id){
        ret = node(a.id, a.hp+b.hp);
    }else if(a.hp > b.hp){
        ret = node(a.id, a.hp-b.hp);
    }else{
        ret = node(b.id, b.hp-a.hp);
    }
    if(ret.hp == 0) ret.id = 0;
    return ret;
}

struct sumbst{
    vector<node> tree;
    int base;
    sumbst(int n, int* arr){
        base = (1<<(int)(ceil)(log2(n+3)))-1;
        tree = vector<node>(base*2+2, node());
        for(int lx = 0; lx < n;lx++)
            tree[lx+base+2] = node(arr[lx], 1);

        for(int lx = base;lx;lx--)
            tree[lx] = tree[lx<<1]+tree[(lx<<1)^1];
    }
    int query(int a, int b){
        node ret;
        for(a += base+1, b += base+3;a^b^1;a>>=1, b>>=1){
            if(~a&1) ret = ret + tree[a^1];
            if(b&1) ret = ret + tree[b^1];
        }
        return ret.id;
    }
};

int arr[500000];

map<int, vector<int> > qmap;

int main(){
    int n, q; scanf("%d %d", &n, &q);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    for(int lx = 0;lx < n;lx++) qmap[arr[lx]].push_back(lx);
   
    sumbst bst(n, arr);
    for(int lx = 0;lx < q;lx++){
        int a, b; scanf("%d %d", &a, &b); a--, b--;
        int id = bst.query(a, b);
        if(id == 0){ printf("0\n"); continue;}
        vector<int>& vec = qmap[id];
        int lowptr = lower_bound(vec.begin(), vec.end(), a) - vec.begin();
        int uppptr = upper_bound(vec.begin(), vec.end(), b) - vec.begin();
        int count = uppptr-lowptr;
        if(count > (b-a+1)/2)
            printf("%d\n", id);
        else
            printf("0\n");
    }
    return 0;
}