hdu 1556 Color the ball (树状数组)_树状数组 color the ball树状数组-程序员宅基地

技术标签: 树状数组  数据结构  

Problem Description

N个气球排成一排,从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0,输入结束。

Output

每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。

Sample Input

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

Sample Output

1 1 1
3 2 1

题解

典型的区间修改单点查询。用树状数组又快又好。这里新学习了一种高级方法,能够在树状数组上进行区间修改。方法是存数的时候就存比前一个数多的那部分,由前缀和来构成这个数,比如先存了第一个数a,那么存第二个数b时就add(b-a, delta)。要取出这个数也不再是sum(b) - sum(b - 1),而是直接sum(b)。那么如何进行区间修改?方法是差分,将l~r的一头一尾分别加上、减去修改的值。这是由于树状数组的性质,在修改时是向上叠加的前缀和的样式,所以在l处加上这个值,后面的数也都加上了这个值;在r - 1处减去这个值,就避免了超出区间的部分也加上了这个值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, cnt = 0, tree[1000010];

int lowbit(int x) {
    return x & (- x);
}

void modify(int x, int delta) {
    while(x <= n) {
        tree[x] += delta;
        x += lowbit(x);
    }
}

int query(int x) {
    int sum = 0;
    while(x) {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    while(~ scanf("%d", &n) && n) {
        memset(tree, 0, sizeof(tree));
        int l, r;
        for(int i = 1; i <= n; i ++) {
            scanf("%d %d", &l, &r);
            modify(l, 1);
            modify(r + 1, -1);
        }
        for(int i = 1; i < n; i ++)
            printf("%d ", query(i));
        printf("%d\n", query(n));
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u010379542/article/details/75674965

智能推荐

mybatis的mapper,sql删除语句_mybatis delflag-程序员宅基地

文章浏览阅读1.5w次。物理删除:直接使用sql :delete <delete id="deleteByExample" parameterType="java.util.Map"> delete from student where id = #{id} </delete>逻辑删除:在设计表时,使用一个字段作为删除标记。del_flag:逻辑删除字段- 0..._mybatis delflag

杭电 最小生成树 2122 Ice_cream’s world III_杭电最小生成树-程序员宅基地

文章浏览阅读496次。Ice_cream’s world IIITime Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1446 Accepted Submission(s): 494Problem Descriptionice_c_杭电最小生成树

C语言字符串输入_c语言输入字符串-程序员宅基地

文章浏览阅读8.3k次,点赞25次,收藏36次。目录1.分配空间2.不幸的gets()函数3.gets()的替代品fgets()函数(和fputs())如果想把一个字符串读入程序,首先必须预留存储该字符串的空间,然后用输入函数获取该字符串。1.分配空间要做的第一件事是分配空间,以储存稍后读入的字符串。假设编写了如下代码: char *name; scanf("%s",name);虽然可能会通..._c语言输入字符串

Ubuntu 上NFS Server安装使用过程_安装nfs-kernel-server后xshell连不上-程序员宅基地

文章浏览阅读557次。实现步骤: 1.服务器端:sudo apt-get install portmap 2.服务器端:sudo apt-get install nfs-kernel-server 3.客户端:sudo apt-get install nfs-common 4.服务器端配置:sudo gedit /etc/exports添加:/home/share 192.168.1.101 *(rw,sync,_安装nfs-kernel-server后xshell连不上

Properties_for (properties pro : pros)-程序员宅基地

文章浏览阅读124次。import java.util.Properties;import java.util.Set;/*Properties方法使用 * Properties经常用来操作key和value都是String类型的数据 * Object setProperty(String key, String value):向Properties中存放key和value String ..._for (properties pro : pros)

你真的会测试吗?-程序员宅基地

文章浏览阅读192次。前段时间公司在做一个专案,关于开发SAP三方交易单据联动的平台,大概功能就是系统里面两家公司交易业务里自动根据销售公司对客户的销售订单生成相应的采购订单和销售订单,包括后续交货单联动创建,开票和发票校验联动创建等。或许你会问为何不用SAP标准的公司间销售(跨公司销售)的功能,因为公司财务觉得此标准功能有财务税务风险而且少了一些单据,不让用。所以开发三方交易联动的平台,满足所有单据生成的同时也可..._sap业务顾问如何测试开发的表单和凭证

随便推点

实时通信技术的架构设计_通讯服务器技术架构图-程序员宅基地

文章浏览阅读1.8k次。一、WEB端实时通信技术对比在WEB端的实时通信技术中,主要有以下几种方式: 1)轮询技术轮询是最简单的一种实时通信技术,易于实现,非常适用于一些小型的应用。其基本原理是这样的,先在客户端设定一个时间间隔,然后在每个间隔里从服务器拉取一次数据,如此反复,进行实时通信。轮询的缺点是显而易见的,若时间间隔过大,则会影响实时性,若时间间隔过小,又会对服务器产生非常大的负担,并_通讯服务器技术架构图

Unix系列shell程序编写_unix bsh-程序员宅基地

文章浏览阅读581次。http://bbs.chinaunix.net/thread-557642-1-1.htmlUnix系列shell程序编写(上) *Shell是什么?   任何发明都具有供用户使用的界面。UNIX供用户使用的界面就是Shell(DOS的command熟悉吧,但UNIX的要强大的多)。 Shell为用户提供了输入命令和参数并可得到命令执行结果的环境。   为了不_unix bsh

谈技术文章翻译的信雅达-下_技术文件翻译 直译 也需要信雅达翻译吗-程序员宅基地

文章浏览阅读4.2k次。 谈技术文章翻译的信雅达-下 Horin|贺勤 Email: [email protected] Blog: http://blog.csdn.net/horin153/ 以前在看国内 Python 达人 limodou 翻译的“Guido van Rossum 博客中文版”中的文章:Python_技术文件翻译 直译 也需要信雅达翻译吗

白皮书 | 京东发布区块链技术实践白皮书-程序员宅基地

文章浏览阅读191次。白皮书 | 京东发布区块链技术实践白皮书导言近日,京东区块链底层引擎JD C..._京东区块链技术实践白皮书

java子类重写父类方法(两同两小一大原则)-程序员宅基地

文章浏览阅读823次。参考资料:https://blog.csdn.net/zjkc050818/article/details/75300796

JS判断鼠标的滚轮滚动方向,鼠标是否在某个元素中 是向上还是向下滚动_如何判断元素身上的滚轮是向上滑还是向下滑-程序员宅基地

文章浏览阅读1.5k次。var x = null; var y = null; $(document).mousemove(function(e){ x = e.pageX; y = e.pageY; }); var scrollFunc = function(e) { var e = e || window.event; var m = null; if(e.wheelDelt..._如何判断元素身上的滚轮是向上滑还是向下滑