洛谷P3567[POI2014]KUR-Couriers(主席樹+二分)

題意：給一個數列，每次詢問一個區間内有沒有一個數出現次數超過一半

題解：

最近比賽太多，都沒時間切水題了，剛好日推了道主席樹裸題，就寫了一下

然後

WA80

WA0

WA90

？？？？？？

結果重新審題發現沒有資料範圍？？？？

哦，原來是500000，我是真的菜

因為必須要一個數出現超過一半

是以這個數肯定會在左子樹和右子樹中總個數和較大的那個裡。

顯然這樣二分找到樹底複雜度是logn的

如果此時樹底這個點的數值大于一半，那麼就輸出這個解，否則puts("0")

以及：不用離散化！！！

代碼如下：

#include<bits/stdc++.h>
#define lson tr[now].l
#define rson tr[now].r
using namespace std;

struct tree
{
    int l,r,sum,val;
}tr[10000050];

int rt[500010],a[500010],n,m,cnt;
map<int,int> mm;

inline int push_up(int now)
{
    tr[now].sum=tr[lson].sum+tr[rson].sum;
}

int insert(int &now,int fa,int l,int r,int pos)
{
    if(!now) now=++cnt;
    if(l==r)
    {
        tr[now].sum=tr[fa].sum+1;
        tr[now].val=l;
        return 0;
    }
    register int mid=(l+r)>>1;
    if(pos<=mid)
    {
        insert(tr[now].l,tr[fa].l,l,mid,pos);
        tr[now].r=tr[fa].r;
    }
    else
    {
        tr[now].l=tr[fa].l;
        insert(tr[now].r,tr[fa].r,mid+1,r,pos);
    }
    push_up(now);
}

inline int query(int a,int b,int l,int r,int tar)
{
    if(l==r)
    {
        if(tr[a].sum-tr[b].sum>=tar) return l;
        else return 0;
    }
    register int mid=(l+r)>>1;
    register int ls=tr[tr[a].l].sum-tr[tr[b].l].sum;
    register int rs=tr[tr[a].r].sum-tr[tr[b].r].sum;
    if(ls>rs) return query(tr[a].l,tr[b].l,l,mid,tar);
    else return query(tr[a].r,tr[b].r,mid+1,r,tar);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        insert(rt[i],rt[i-1],1,500000,a[i]);
    }
    int from,to;
    while(m--)
    {
        scanf("%d%d",&from,&to);
        register int mid=(to-from+1)/2+1;
        printf("%d\n",b[query(rt[to],rt[from-1],1,500000,mid)]);
    }
}