2019/6/13 day12 解题日志

2019-06-13

字数统计: 461字 | 阅读时长: 2分

day12

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半。
如果有，输出该数字，否则输出0。

主席树

已知查询区间为$[l,r]$，要使得存在某个数字出现次数大于$(r-l+1)$，必然存在所有维护该数字的区间，它的区间和都是大于$(r-l+1)$，且对于当前区间的左右儿子，最多只存在一个子区间，仍然满足当前性质，那么直接递归到叶子结点便可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
int n,q,a[maxn];
int T[maxn],lson[maxn*30],rson[maxn*30],c[maxn*30],tot;
int build(int l,int r){
    int ret=tot++;
    if(l!=r){
        int mid=l+r>>1;
        lson[ret]=build(l,mid);
        rson[ret]=build(mid+1,r);
    }return ret;
}
int update(int rt,int pos){
    int nrt=tot++;
    c[nrt]=c[rt]+1;
    int ret=nrt,l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[nrt]=tot++,rson[nrt]=rson[rt];
            nrt=lson[nrt];rt=lson[rt];r=mid;
        } else {
            lson[nrt]=lson[rt],rson[nrt]=tot++;
            nrt=rson[nrt];rt=rson[rt];l=mid+1;
        }
        c[nrt]=c[rt]+1;
    }
    return ret;
}
int query(int lrt,int rrt,int lim){
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(c[lson[rrt]]-c[lson[lrt]]>lim){
            lrt=lson[lrt];rrt=lson[rrt];
            r=mid;
        } else if(c[rson[rrt]]-c[rson[lrt]]>lim){
            lrt=rson[lrt];rrt=rson[rrt];
            l=mid+1;
        } else return 0;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    T[0]=build(1,n);
    for(int i=1;i<=n;i++){
        T[i]=update(T[i-1],a[i]);
    }
    int l,r;
    while(q--){
        scanf("%d%d",&l,&r);
        printf("%d\n",query(T[l-1],T[r],(r-l+1)/2));
    }
    return 0;
}

分块

留坑。