HDU 1556树状数组-程序员宅基地

传送门： HDU 1556

题解

树状数组模板题
区间染色 + 统计次数
向上查询，向下统计
先把a之后的区间加一次染色更新，再把b之后减一次染色更新，这样[a, b]데染色更新就完成了

AC code:

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

#define lowbit(x) (x & (-x))
#define LL long long 
#define debug 1

const int maxn(100005);
const int mod(1e9 + 7);

int c[maxn];

int n;



void add(int x, int y, int v) {

    for (int i = x; i <= n; i += lowbit(i)) {
        c[i] += v;
    }

    for (int i = y + 1; i <= n; i += lowbit(i)) {
        c[i] -= v;
    }
}

int getSum(int x) {
    int res = 0;

    for (int i = x; i; i -= lowbit(i)) {
        res += c[i];
    }

    return res;
}

int main() {
#if debug
    freopen("in.txt", "r", stdin);
#endif //debug

    int a, b;

    while (cin >> n, n) {

        memset(c, 0, sizeof(c));

        for (int i = 1; i <= n; ++i) {
            cin >> a >> b;
            add(a, b, 1);
        }

        for (int i = 1; i <= n; i++) {
            int ans = getSum(i);
            cout << ans << (i == n ? "\n" : " ");
        }
    }

    return 0;
}

本文链接：https://blog.csdn.net/ADjky/article/details/53224990

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【新年福利】2019年值得一用的8款协作工具_摹客rp优惠-程序员宅基地

或许你是掩埋在爆炸信息里的运营自媒体人，或许你是奔走于产品线上的产品经理，或许你是被各位甲方爸爸压迫的设计师，或许你是办公室里被各种Deadline搞得焦头烂额的职场人......无论你是谁，无论你从事哪份工作，在这个优胜劣汰的职场环境里，能力几乎成为了唯一的话语权，孤军奋战注定失败，唯有团队齐心协力才能度过寒冬。你需要优质的工作模式最大程度得保障高效工作，无协作，不效率，2019年值得一用的..._摹客rp优惠

C++函数学习（三）-程序员宅基地

60 size 的用法size是由string vector 和bitset定义的函数，分别用于返回字符个数，元素个数和二进制位的数。string和vector的size成员函数用以返回size_type类型的值。bitset返回size_t的值。用法，例如stringstring st("fddddddddgs");cout打印st中的字符个数size其实就是计算

android Monkey test测试_android 的monkey test-程序员宅基地

下面介绍一种Monkey测试方法：单一模块Monkey测试以下这条Monkey指令为例：monkey -s 12 --throttle 450 -p com.android.cameraswitch --kill-process-after-error --ignore-timeouts --ignore-security-exceptions -v 10000 这条_android 的monkey test

python利用matplotlib做饼图_python利用matplotlib库绘制饼图的方法示例-程序员宅基地

介绍matplotlib 是python最著名的绘图库，它提供了一整套和matlab相似的命令API，十分适合交互式地进行制图。而且也可以方便地将它作为绘图控件，嵌入GUI应用程序中。它的文档相当完备，并且 Gallery页面中有上百幅缩略图，打开之后都有源程序。因此如果你需要绘制某种类型的图，只需要在这个页面中浏览/复制/粘贴一下，基本上都能搞定。matplotlib的安装方法可以点击这里这篇..._3. 请使用python中的matplotlib库绘制以下数据的饼状图,并添加适当的标题和图例。

如何在Java中正确使用Apache Commons数学库中的ZipfDistribution？_org.apache.commons.math3.distribution.zipfdistribu-程序员宅基地

javaapache-commons-mathzipf温馨提示：将鼠标放在语句上可以显示对应的英文。或者切换至中英文显示我想基于遵循Zipf分布的单词（来自字典）创建数据源（Java）。因此，我来谈谈Apache commons库的ZipfDistribution和NormalDistribution。不幸的是，很少有关于如何使用这些类的信息。我尝试进行一些测试，但不确定是否以正确的方式使用它。我只关注每个构造函数的文档中写的内容。但是结果似乎并不“分布均匀..._org.apache.commons.math3.distribution.zipfdistribution

目标检测入门知识以思考（写于2021.11）-程序员宅基地

刚入CV时，对于目标检测以及相关内容的简单理解