TSOJ 1352 – 线段树 – 模板备份

题目

题目描述

第三次选择那些大晴天的日子,第三次行走在孤单的海岸线,第三次静静地种更多的花给自己看~

我们假设把海岸线分为n块,每块的分别标记为1…n,每块都可以种花,每次种花可以选择某个[left,right]的闭区间,每块种上一朵花.经过m次种花操作后, 输入t次区间, 根据输入的区间,求该区间内花的总数.

注意这一次,我们要看更多次的花儿，所以在第一行要输入看花的次数t

输入描述

多组输入

对每组输入，第一行有三个整数n m t,分别代表总块数和种花的次数以及我们希望查询区间的次数.(1 <= n, m, t<= 100000)

接下来的m行, 每行两个整数 L,R 代表[L,R]区间内每块种上一朵花.(1 <= L <= R <= n)

接下来的t行, 每行输入两个整数 a,b 代表最后要查询的花的总数的区间.(1 <= a <= b <= n)

输出描述

每组输入中, 对每次查询, 输出区间[a,b]内花的总数

样例输入

5 2 2
1 5
1 2
2 3
3 4

样例输出

3
2

样例说明

第一行的三个数5 2 2 分别代表一共有5块可以种花的地方, 种花2次, 种完花后要查询2次

下面的两行 1 5 以及 1 2 表示在区间[1,5],[1,2]分别种一次花,不难算出,种完花后每个位置花的总数分别为2 2 1 1 1,最后两行2 3 以及3 4 表示我们要分别求出[2,3],[3,4]区间内花的总数,所以输出的结果分别为3 2

分析

可用线段树次选解决的裸题。区间更新，区间查询。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>


#define N 110000

using namespace std;

struct Node {
    int l, r, m, s, t;
} m[4 * N];

void build(int i, int l, int r) {
    m[i].l = l;
    m[i].r = r;
    m[i].m = (l + r) / 2;
    if (l >= r) return;
    build(2 * i, l, m[i].m);
    build(2 * i + 1, m[i].m + 1, r);
}


void update(int i, int l, int r, int v) {
    if (l <= m[i].l && m[i].r <= r)
        m[i].t += v;
    else {
        if (r > m[i].m)
            update(2 * i + 1, l, r, v);
        if (l <= m[i].m)
            update(2 * i, l, r, v);
        m[i].s = m[2 * i].s + (m[2 * i].r - m[2 * i].l + 1) * m[2 * i].t
                 + m[2 * i + 1].s + (m[2 * i + 1].r - m[2 * i + 1].l + 1) * m[2 * i + 1].t;
    }
}

int select(int i, int l, int r) {
    int ans = 0;
    if (l <= m[i].l && m[i].r <= r) {
        ans =  m[i].s + (m[i].r - m[i].l + 1) * m[i].t;
    } else {
        if (m[i].t != 0) {
            m[i].s += (m[i].r - m[i].l + 1) * m[i].t;
            m[2 * i].t += m[i].t;
            m[2 * i + 1].t += m[i].t;
            m[i].t = 0;
        }
        if (r > m[i].m)
            ans += select(2 * i + 1, l, r);
        if (l <= m[i].m)
            ans += select(2 * i, l, r);
    }
    return ans;
}



int main() {

    int n, k, l;
    while (~scanf("%d %d %d", &n, &k, &l)) {
        memset(m, 0, sizeof(m));
        build(1, 1, n);
        int c, d;
        while (k--) {
            scanf("%d %d", &c, &d),
                  update(1, c, d, 1);
        }
        while (l--) {
            scanf("%d %d", &c, &d),
                  printf("%d\n", select(1, c, d));
        }
    }
    return 0;
}

 

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.