【bzoj3223】Tyvj 1729 文艺平衡树

2014年7月22日6,65924

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n)  m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字,表示原始序列经过m次变换后的结果

Sample Input

5 31 31 31 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

题解

4:22 *1

7:22 *1

直接splay。。。 区间翻转而已。。。

 

  • 涵丶2015年4月4日 下午11:33 回复

    一直不理解id数组到底是什么含义。。

    #1  
    • hzwer2015年4月5日 上午12:24 回复
      admin

      噢这题是没用的

      #11
      • 涵丶2015年4月5日 上午10:11 回复

        那在一般的序列维护题目里面id数组是什么含义?

        #12
        • hzwer2015年4月5日 上午10:54 回复
          admin

          详见维修数列

          #13
  • 张虎2015年4月15日 上午8:32 回复

    那个find函数到底是find什么鬼

    #2  
    • hzwer2015年4月15日 上午11:49 回复
      admin

      找K大,即序列第K个数

      #21
      • 张虎2015年4月15日 下午1:46 回复

        也就是说现在不满足二叉搜索树的性质是吗

        #22
        • hzwer2015年4月15日 下午2:04 回复
          admin

          序列顺序与大小关系不可同时维护

          #23
          • 张虎2015年4月15日 下午2:45

            这样不是序列顺序和大小关系都不满足二叉搜索树吗

            #24
          • hzwer2015年4月15日 下午5:04
            admin

            序列编号满足

            #24
          • 张虎2015年4月15日 下午5:08

            好像大概明白了,谢谢黄学长

            #24
  • ztc2015年8月9日 上午7:22 回复

    看黄学长主页学过来的

    #3  
  • Alisa2016年1月17日 下午7:29 回复

    为什么rever中是y=find(rt,r+2);?

    #4  
    • hzwer2016年1月17日 下午11:56 回复
      admin

      要操作l+1到r+1这段,把l转到根,r+2转到根的右儿子

      #41
      • Alisa2016年1月18日 上午9:47 回复

        原来是酱紫,懂了

        #42
      • charlie0032016年7月7日 下午5:24 回复

        请问黄学长加了两个虚根为什么只加1?

        #42
        • hzwer2016年7月7日 下午9:16 回复
          admin

          你要操作1,n这个序列,需要对0和n+1作旋转

          #43
  • Sigma_Poet2016年1月30日 上午10:33 回复

    黄学长,你的SPLAY中的splay和rotate都是传的两个参数,如果现在要进行启发式合并(也就是有多棵Splay,有许多根),那么int &k那里肯定要传的是当前结点所在的Splay的根。怎么维护这个根结点啊??

    #5  
    • hzwer2016年1月30日 下午11:33 回复
      admin

      你肯定要用个数组把splay的根存起来呗

      #51
  • Sigma_Poet2016年2月13日 下午3:31 回复

    学长,你为什要建1..n + 2 区间的Splay树,而并不是1..n

    #6  
    • will71012016年4月6日 下午9:32 回复

      帮学长回答一下。。。1和n+2是两侧的哨兵节点,这样就可以在访问2..n+1区间(左右边界)的时候提起0和n+2节点。

      #61
  • DJRAA122016年6月26日 下午4:33 回复

    求问黄学长,为什么有区间翻转操作的时候,splay不需要pushdown…做这类题一直搞不懂

    #7  
    • hzwer2016年6月26日 下午9:17 回复
      admin

      因为find的时候pushdown了

      #71
  • 苦读依旧2016年12月25日 下午4:42 回复

    id数组是不是为了省空间啊

    #8