【bzoj1251】序列终结者

2014年7月21日3,41417

Description

网上有许多题,就是给定一个序列,要你支持几种操作:A、B、C、D。一看另一道题,又是一个序列 要支持几种操作:D、C、B、A。尤其是我们这里的某人,出模拟试题,居然还出了一道这样的,真是没技术含量……这样 我也出一道题,我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠,没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列,每个序列的元素是一个整数(废话)。要支持以下三种操作: 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转,比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。

Input

第一行两个整数N,M。M为操作个数。 以下M行,每行最多四个整数,依次为K,L,R,V。K表示是第几种操作,如果不是第1种操作则K后面只有两个数。

Output

对于每个第3种操作,给出正确的回答。

Sample Input

4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4

Sample Output

2
【数据范围】
N<=50000,M<=100000。

题解

splay练习题,上网搜索伸展树有很多材料

 

  • mxh2014年4月22日 下午7:34 回复

    变权限题了5555

    #1  
    • hzwer2014年4月23日 下午5:50 回复
      admin

      我是权限狗0.0

      #11
  • zhouleyu2014年4月30日 下午2:26 回复

    变权限题了5555

    #2  
  • Crazyxx2014年12月14日 上午8:22 回复

    4.9 *1
    7.21 *3
    我一直搞不懂您这些数字是什么意思,难道是日期*刷的次数么TAT

    #3  
    • hzwer2014年12月14日 上午10:09 回复
      admin

      日期*刷的次数

      #31
  • 涵丶2015年4月5日 下午2:01 回复

    mx[0]=-inf; 为什么少这句话就会WA。。

    #4  
    • hzwer2015年4月5日 下午2:02 回复
      admin

      因为有可能最大值是负数

      #41
      • 涵丶2015年4月5日 下午2:03 回复

        哦。。。

        #42
      • 涵丶2015年4月5日 下午2:04 回复

        还是不太明白。。

        #42
      • 涵丶2015年4月5日 下午2:08 回复

        哦我懂了 这个是把所有叶子的儿子的mx设成-INF

        #42
  • M_axssi2016年1月3日 下午2:13 回复

    黄学长 rotate 到底是干什么的啊

    #5  
  • %%%hzwer2016年1月12日 上午9:40 回复

    为什么build(1,n+2,0)是n+2

    #6  
    • hzwer2016年1月12日 下午5:05 回复

      splay首尾放个哨兵

      #61
      • %%%hzwer2016年1月12日 下午5:57 回复

        可以用来干什么。。。有什么特别的作用吗?

        #62
        • hzwer2016年1月12日 下午11:35 回复
          admin

          操作1-n的序列,把0旋转到根,把n+1旋转到根的右子树

          #63