[POI2014]KUR-Couriers

摘要

给一个数列,每次询问一个区间内有没有一个数出现次数严格超过一半. .

复习一下主席树~

区间 对应版本 的权值线段树的差。每次查询当前结点的左右儿子结点的大小,哪一个的大小超过了区间长度的一半就转移到哪个去,否则返回 0 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1<<24,MAXA=2e6;
int n,m,a[N];
int tot,rt[N],lc[N],rc[N],val[N];//val 表示值域对应区间中的数的个数

int build(int l,int r){int u=++tot,mid=(l+r)>>1;
    if(l<r)lc[u]=build(l,mid),rc[u]=build(mid+1,r);
    return u;
}
int modify(int u,int v,int l=1,int r=MAXA){// 返回结点 u 的副本结点
    int u2=++tot,mid=(l+r)>>1;// 新建结点
    val[u2]=val[u]+1;
    if(l==r)return u2;
    if(v<=mid)lc[u2]=modify(lc[u],v,l,mid),rc[u2]=rc[u];
    else lc[u2]=lc[u],rc[u2]=modify(rc[u],v,mid+1,r);
    return u2;
}
int len;
int query(int ul,int ur,int l=1,int r=MAXA){assert(val[2]==0);
    if(l==r)return l;// 找到
    int mid=(l+r)>>1,vl=val[lc[ur]]-val[lc[ul]],vr=val[rc[ur]]-val[rc[ul]];
    if(vl*2>len)return query(lc[ul],lc[ur],l,mid);
    else if(vr*2>len) return query(rc[ul],rc[ur],mid+1,r);
    else return 0;
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    rt[0]=build(1,MAXA);
    for(int i=1;i<=n;i++)rt[i]=modify(rt[i-1],a[i]);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        len=r-l+1;
        int k=query(rt[l-1],rt[r]);
        printf("%d\n",k);
    }
    return 0;
}

  转载请注明: Sshwy's Blog [POI2014]KUR-Couriers

 上一篇
[POI2014]HOT-Hotels [POI2014]HOT-Hotels
摘要 题意:一颗无根树,每条边长度相同。选 3 个点两两距离相等,有多少种方案? . 不难证明三条路径交汇于一个中心点。以这个中心点为根的话,那么这三个结点深度相同。于是我们枚举根结点,并统计每一个深度的结点数(注意
2019.04.06
下一篇 
[POI2007]TET-Tetris Attack [POI2007]TET-Tetris Attack
摘要 题意:给定一个长度为 的序列, 各出现两次,可以交换相邻两项,两个同样的数相邻会消失,求把所有数对消的最小交换次数,输出方案。 . 一看就是一个树状数组的问题,关键是
2019.04.05
  目录