「JoyOI1473」校门外的树3

2013年12月30日4,8534

描述 Description

校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作:
K=1,读入l,r表示在l~r之间种上的一种树
K=2,读入l,r表示询问l~r之间能见到多少种树
(l,r>0)

输入格式 InputFormat

第一行n,m表示道路总长为n,共有m个操作
接下来m行为m个操作

输出格式 OutputFormat

对于每个k=2输出一个答案

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

题解

将[a,b]种上一种树

这个修改操作影响的询问满足,询问区间与[a,b]有交,转化为统计总修改数-与某询问交为空集的修改数

对于一个修改操作[l,r],与它为空集的询问[a,b]满足a∈[1,l-1]或者b∈[r+1,n]

用两棵线段树维护

修改[l,r],将第一棵的[1,l-1]区间+1,第二棵[r+1,n]区间+1

询问[a,b],答案为之前的修改数-(第一棵单点询问b+第二棵单点询问a)

代码中线段树结点的l,r其实就是两棵线段树。。。

标记永久化

 

avatar
3 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Hello_BABY_OvOhzwercyy489 Recent comment authors
  Subscribe  
提醒
Hello_BABY_OvO

黄学长,建立插入的补集时右端不是应该建立到(b+1,n+1)吗???如果这样,插入到n中,b+1>n就会爆炸。。。虽说没这个数据。。。

kyeremalprime

黄学长..答案应该是 [之前的修改数 – (第一棵单点询问b + 第二棵单点询问a)] 吧..
就是在左树中找右端点,右树中找左端点吧..

cyy489
cyy489

请问大神,此题您的程序中的tr .l和tr .r是什么意思呢?