#LX0017. 线段树

线段树

题目描述

小明有一棵线段树。

啥是线段树呢?你可以想象成,一开始,你有一个区间[1,n][1,n],然后,你可以取中点x=1+n2x=\frac{1+n}{2},把它划分成两个区间[1,x],[x+1,n][1,x],[x+1,n]。(之前那个区间[1,n][1,n]也还在的哦)

然后,你可以继续划分下去,直到把每一个区间都划分成长度为11为止,下图就是一棵线段树,维护了区间[1,10][1,10]的信息。

img

假设线段树上,每个节点都存储了它表示的区间内所有元素的信息(比如区间的和)。

那么,当我想知道一个区间[l,r][l,r]的信息的时候,我一定可以在线段树上找到一些区间,这些区间互相没有交集,且并起来刚好是区间[l,r][l,r]

比如,我在上图的线段树中,要查询[4,8][4,8]的信息,那么我找到[4,5],[6,8][4,5],[6,8]两个区间,就可以表示区间[4,8][4,8]的信息了。(把[6,8][6,8]替代成[6,7],[8,8][6,7],[8,8]显然也是合法的策略,但是这样选择的区间更多了,不够优秀)。

我们称,对于一次查询[l,r][l,r],我们需要用到的区间个数为fl,rf_{l,r},比如上图中f4,8=2,f1,6=2f_{4,8}=2,f_{1,6}=2

我们的问题是:给定线段树根节点所表示的区间范围是[1,n][1,n],以及有qq次查询,第ii次查询是[li,ri][l_i,r_i],假设你可以在最初时候自由的选择区间分割的位置,i=1qfli,ri\sum_{i=1}^{q} f_{l_i,r_i}最小是多少?

输入格式

第一行输入n,qn,q

接下来qq行,每行两个数字li,ril_i,r_i

输出格式

一个数字表示答案。

样例输入 #1

4 2
1 3
4 4

样例输出 #1

2

样例解释 #1

对于我们来说,我们可以在第一层分割时候,把区间[1,4][1,4]分割成[1,3],[4,4][1,3],[4,4],这样两个查询都只需要一次操作。

样例输入 #2

5 3
1 3
3 5
2 4

样例输出 #2

5

样例解释 #2

我们在第一层把区间分割成[1,2],[3,5][1,2],[3,5],然后把[3,5][3,5]分割成[3,4],[5,5][3,4],[5,5][3,4][3,4]分割成[3,3],[4,4][3,3],[4,4][1,2][1,2]分割成[1,1],[2,2][1,1],[2,2]

这样,对于[1,3][1,3]的查询,我们需要用到两个区间[1,2],[3,3][1,2],[3,3]

对于[3,5][3,5]的查询,我们需要用到[3,5][3,5]一个区间。

对于[2,4][2,4]的查询,我们需要用到[2,2],[3,4][2,2],[3,4]两个区间。

样例输入 #3

10 8
1 5
2 6
2 4
2 8
2 9
3 5
3 6
1 10

样例输出 #3

11

数据范围

对于30%的数据:保证n10,q20n\leq 10,q\leq 20

对于50%的数据:保证n,q100n,q\leq 100

对于70%的数据:保证n,q500n,q\leq 500

对于100%的数据:保证$1\leq n \leq 500,1\leq q\leq 10^5,1\leq l_i\leq r_i\leq n$。