SS's Trace

Sirius's Blog

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 分别代表一共有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

分析

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

代码

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注