【bzoj3678】wangxz与OJ

2014年8月13日1,8253

Description

某天,wangxz神犇来到了一个信息学在线评测系统(Online Judge)。由于他是一位哲♂学的神犇,所以他不打算做题。他发现这些题

目呈线性排列,被标记为1~n号,每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。

1、他可以在某个位置插♂入一些难度值特定的题目。

2、他可以吃♂掉(删除)一段题目。

3、他可以查询某个位置的题目的难度值。

维护一个初始有n个元素的序列(标记为1~n号元素),支持以下操作:

0 p a b (0<=p<=当前序列元素个数) (a<=b) 在p位置和p+1位置之间插入整数:a,a+1,a+2,…,b-1,b。若p为0,插在序列最前面;

1 a b (1<=a<=b<=当前序列元素个数) 删除a,a+1,a+2,…,b-1,b位置的元素;

2 p (1<=p<=当前序列元素个数) 查询p位置的元素。

Input

输入第一行包括两个正整数n(1<=n<=20000),m(1<=m<=20000),代表初始序列元素个数和操作个数。

接下来n个整数,为初始序列元素。

接下来m行,每行第一个为整数sym,

若sym=0,接下来有一个非负整数p,两个整数a,b;

若sym=1,接下来有两个正整数a,b;

若sym=2,接下来有一个正整数p;

p、x、y的含义及范围见题目描述。

在任何情况下,保证序列中的元素总数不超过100000。

保证题目涉及的所有数在int内。

Output

对每个sym=2,输出一行,包括一个整数,代表询问位置的元素。

Sample Input

5 3
1 2 3 4 5
0 2 1 4
1 3 8
2 2

Sample Output

2

题解

为何此题rope要用short T T

过了几天,发现改了数据。。。于是rope被卡了

 

  • smkx2014年8月14日 上午10:21 回复

    貌似这种做法的最坏复杂度是100000*m的吧?

    #1  
    • hzwer2014年8月14日 下午12:01 回复
      admin

      但是我想不到靠谱做法

      #11
      • smkx2014年8月14日 下午1:11 回复

        splay维护,每次只加一个点,要动的时候在分裂

        #12