BZOJ 2223: [Coci 2009]PATULJCI 主席树-蒲公英云

BZOJ 2223: [Coci 2009]PATULJCI 主席树

心已赠人 2021-11-17 16:24 328阅读 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; 
}