BZOJ 2223: [Coci 2009]PATULJCI 主席树

心已赠人 2021-11-17 16:24 185阅读 0赞

题目描述：动态求出现次数大于等于区间一半长度的数字.  
题解： 对序列维护一个主席树即可.

#include<bits/stdc++.h>
    #define maxn 300001  
    #define mid ((l+r)>>1) 
    using namespace std;
    inline void setIO(string s)
    {
        string in=s+".in"; 
        freopen(in.c_str(),"r",stdin); 
    }
    int cnt, cc=0; 
    int ls[maxn*20],rs[maxn*20],sumv[maxn*20],root[maxn]; 
    void build(int l,int r,int &o)
    {
        o=++cnt; 
        if(l==r) return; 
        if(mid>=l) build(l,mid,ls[o]); 
        if(r>mid) build(mid+1,r,rs[o]);  
    }
    int update(int l,int r,int k,int x)
    {
        int oo=++cnt;
        sumv[oo]=sumv[x]+1; 
        ls[oo]=ls[x], rs[oo]=rs[x]; 
        if(l==r) return oo; 
        if(k<=mid) ls[oo]=update(l,mid,k,ls[x]);  
        else rs[oo]=update(mid+1,r,k, rs[x]);   
        return oo; 
    }   
    int query(int u,int v,int l,int r)
    { 
        if(l==r)
        {      
            if(sumv[v]-sumv[u] > cc) return l; 
            return -1; 
        }
        int tmp=sumv[ls[v]]-sumv[ls[u]];            
        if(tmp > cc) return query(ls[u], ls[v], l, mid); 
        else return query(rs[u], rs[v], mid + 1, r); 
    }
    int main()
    {
        // setIO("input"); 
        int n,m,i,a,Q,l,r; 
        scanf("%d%d",&n,&m);          
        build(1,m,root[0]); 
        for(i=1;i<=n;++i)     
        {
            scanf("%d",&a); 
            root[i]=update(1,m,a,root[i-1]); 
        } 
        scanf("%d",&Q);
        while(Q--)
        {
            scanf("%d%d",&l,&r); 
            cc=(r-l+1)>>1;  
            a = query(root[l-1], root[r], 1, m); 
            if(a==-1) printf("no\n"); 
            else printf("yes %d\n", a); 
        }
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11066429.html