注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1556  

2012-08-03 17:21:47|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
线段树
题意:开始1到N全为0,给出几个区间,区间内每个数加1,最后输出1到N每个数一共加了几次
/*
 * fudq.cpp
 *
 *  Created on: 2012-08-03
 *      Author: fudq
 */
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
#define N 100010
struct Node
{
    int l,r,num;
};
Node node[3*N];

void Build(int left,int right,int t)
{
    node[t].l=left;
    node[t].r=right;
    if(left==right)
        node[t].num=0;
    else
    {
        int mid;
        mid=(left+right)/2;
        Build(left,mid,t*2);
        Build(mid+1,right,t*2+1);
        node[t].num=0;
    }
}

void Update(int left,int right,int t,int val)
{
    if(node[t].l==left && node[t].r==right)
    {
    node[t].num+=val;
    return ;
    }
    int mid=(node[t].l+node[t].r)/2;
    if(right<=mid)
    Update(left,right,t*2,val);
    else if(left>mid)
    Update(left,right,t*2+1,val);
    else
    {
    Update(left,mid,t*2,val);
    Update(mid+1,right,t*2+1,val);
    }
}

int Query(int left,int right,int t)
{
    if(left==node[t].l && right==node[t].r)
        return node[t].num;
    Update(node[2*t].l,node[2*t].r,2*t,node[t].num);
    Update(node[2*t+1].l,node[2*t+1].r,2*t+1,node[t].num);
    node[t].num=0;
    int mid=(node[t].l+node[t].r)/2;
    if(right<=mid)
    return Query(left,right,t*2);
    else if(left>mid)
    return Query(left,right,t*2+1);
    else
    return Query(left,mid,t*2)+Query(mid+1,right,t*2+1);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int n,a,b,i;
    while(scanf("%d",&n)!=EOF && n)
    {
        Build(1,n,1);
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&a,&b);
            Update(a,b,1,1);
        }
        for(i=1;i<=n;i++)
        {
        if(i!=1)
        printf(" ");
        printf("%d",Query(i,i,1));
        }
        printf("\n");
    }
    return 0;
}

  评论这张
 
阅读(203)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018