题目
题目描述
第三次选择那些大晴天的日子,第三次行走在孤单的海岸线,第三次静静地种更多的花给自己看~
我们假设把海岸线分为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.