【bzoj3110】[Zjoi2013]K大数查询

2014年10月8日7,62627

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M
接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output


1
2
1

HINT

N,M<=50000,N,M<=50000a<=b<=N

1操作中abs(c)<=N

2操作中abs(c)<=Maxlongint

题解

我写的树套树做法,第一位权值,第二位区间

写的常数太渣了。。。标记还是永久化比较好。。。

对于区间[l,r],将权值在此之内的修改建立一棵普通线段树。这样对于一个询问,就可以类似二分答案,首先看权值在[1,mid]中有几个在询问的区间中,如果<排名,就往右,否则往左。

注:本题数据没有负数TAT

 

  • 2015年8月27日 下午1:28 回复

    求问黄学长您这个程序似乎RE了?

    #1  
    • hzwer2015年8月29日 下午11:36 回复
      admin

      刚刚交了一遍AC了啊

      #11
  • Dog liuyujun2016年2月17日 下午4:33 回复

    妹控黄学长-><-

    #2  
    • hzwer2016年2月17日 下午5:24 回复
      admin

      何以见得?

      #21
      • Dog liuyujun2016年2月17日 下午6:56 回复

        换个说法,萝莉控吧~~~
        话说黄学长,难道混2次元OI能够学得好吗,感觉好多OI大神都混2次元啊

        #22
        • hzwer2016年2月18日 上午12:13 回复
          admin

          讲道理我并不是萝莉控。。。也许是个*(和谐)控
          是因为天天上网才会去看奇怪的东西吧
          感觉很多OI大神是哲学家呢0、0

          #23
          • Scarlet2016年2月19日 下午8:24

            讲道理萝莉赛高

            #24
          • 张丁天2016年2月21日 上午11:56

            萝莉即是正义OAQ

            #24
          • hop2016年2月20日 下午7:45

            哲♂学?

            #24
    • 魔法炮2016年2月17日 下午5:34 回复

      额这个 貌似“23333”会被多说直接当做垃圾评论

      #21
  • 鸭神2016年3月25日 下午9:14 回复

    Orz黄学长。。。但是他们加强了数据。。现在有负数了诶。。您的代码没有离散化。。

    #3  
    • hzwer2016年3月25日 下午10:29 回复
      admin

      – –

      #31
      • 鸭神2016年3月26日 下午4:53 回复

        嘛。。。其实并不需要在意。。。

        #32
        • sxb_2012016年3月27日 下午8:01 回复

          不仅仅有负数吧 还需要 LL

          #33
          • 鸭神2016年3月27日 下午8:11

            不需要吧。。我没有开啊。。也过了。

            #34
    • neither2016年3月28日 下午7:56 回复

      为啥我是没开负数但是需要开ll

      #31
      • 鸭神2016年3月28日 下午8:52 回复

        什么鬼!!!!反正加个离散就可以过了。。也许是离散和没离散的关系吧。。

        #32
        • neither2016年3月29日 下午6:02 回复

          我没离散……ll可能是因为标记永久化的缘故?

          #33
  • yww2016年7月3日 下午3:54 回复

    现在要longlong了

    #4  
  • 小蒟蒻2017年1月18日 下午5:24 回复

    黄学长您代码 WA 了啊!!!大视野数据是有负数的,而且数字个数会爆 int!

    #5  
    • 地蚕包子2017年1月18日 下午8:03 回复

      大哥您先看看黄学长什么时候写的这题好吗……

      #51
      • 小蒟蒻2017年1月20日 上午9:28 回复

        所以要尽量做到实时更新啊。。。程序的 bug 跟日期又没有关系。。。

        #52
    • 12017年1月21日 上午10:19 回复

      这么多道题
      更新。。。。。。。。。。。。。。。
      还实时

      #51