【tyvj1473】校门外的树3

2013年12月30日2,7104

描述 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其实就是两棵线段树。。。

标记永久化

 

  • cyy4892015年7月28日 下午9:50 回复

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

    #1  
    • hzwer2015年7月29日 上午11:48 回复
      admin

      在题解中增加了说明

      #11
  • kyeremalprime2015年9月8日 下午3:40 回复

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

    #2  
    • hzwer2015年9月13日 下午7:08 回复
      admin

      是的。。。

      #21