频道栏目
首页 > 考试 > 其他 > 正文

BZOJ 1112: [POI2008]砖块Klo 线段树维护区间中位数

2016-11-05 10:02:06      个评论    来源:NeighThorn的博客  
收藏   我要投稿

代码如下:

#include
#include
#include
#include
//by NeighThorn
#define inf 100000000000
using namespace std;
const int maxn=100000+5,maxh=1000000+5;
int n,k,h[maxn],m,midnum;
long long ans;
struct Tree{
    int l,r,cnt;
    long long sum;
}tree[maxh*4];
struct M{
    int cnt;
    long long sum;
    M(long long x=0,int y=0){
        sum=x,cnt=y;
    }
}aql,anqila;
inline int read(void){
    char ch=getchar();int x=0;
    while(!(ch>='0'&&ch<='9'))
        ch=getchar();
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void build(int l,int r,int tr){
    tree[tr].l=l,tree[tr].r=r,tree[tr].sum=tree[tr].cnt=0;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(l,mid,tr<<1);build(mid+1,r,tr<<1|1);
}
inline void change(int pos,int val,int tr){
    if(tree[tr].l==tree[tr].r){
        tree[tr].cnt+=val;tree[tr].sum+=val*pos;
        return;
    }
    int mid=(tree[tr].l+tree[tr].r)>>1;
    if(pos<=mid)
        change(pos,val,tr<<1);
    else
        change(pos,val,tr<<1|1);
    tree[tr].cnt=tree[tr<<1].cnt+tree[tr<<1|1].cnt;
    tree[tr].sum=tree[tr<<1].sum+tree[tr<<1|1].sum;
}
inline int querynum(int num,int tr){
    if(tree[tr].l==tree[tr].r)
        return tree[tr].l;
    if(tree[tr<<1].cntr)
        return M(0,0);
    if(tree[tr].l==l&&tree[tr].r==r)
        return M(tree[tr].sum,tree[tr].cnt);
    int mid=(tree[tr].l+tree[tr].r)>>1;
    if(r<=mid)
        return querysum(l,r,tr<<1);
    else if(l>mid)
        return querysum(l,r,tr<<1|1);
    else{
        M tmp=querysum(l,mid,tr<<1),temp=querysum(mid+1,r,tr<<1|1);
        tmp.cnt+=temp.cnt,tmp.sum+=temp.sum;
        return tmp;
    }
}
signed main(void){
    n=read();k=read();m=0;
    for(int i=1;i<=n;i++)
        h[i]=read(),m=max(m,h[i]);
    if(k==1){
        puts("0");return 0;
    }
    build(0,m,1);midnum=(1+k)>>1;
    for(int i=1;i<=k;i++)
        change(h[i],1,1);
    int lala=querynum(midnum,1);aql=querysum(0,lala-1,1),anqila=querysum(lala+1,m,1);ans=aql.cnt*lala-aql.sum+anqila.sum-lala*anqila.cnt;
//  cout<<"lala"<
相关TAG标签 BZOJ 编程
上一篇:ZOJ 1111 &PE 54 oker hands(大模拟扑克)
下一篇:POJ 3693 Maximum repetition substring(后缀数组[重复次数最多的连续重复子串])
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站