2352. [HZOI 2015] 阿瑞

【题目描述】

维护一个序列支持以下操作

1 l r 把第r个数移动到第l个数的前面

2 x y 在第x个数之前插入一个值为y的数

3 x 把第x个位置上的数删掉

4 l r d 询问序列第l到第r个数有多少个数为d

【输入格式】

第一行一个数N,表示开始序列有N个数

接下来一行有N个数,表示序列中每个数的值

之后有一个数M,表示M个操作

接下来M行,每行是一个操作,操作见题目描述

【输出格式】

对于每个询问输出一行一个数,表示对应的答案

【样例输入】

100

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

100

2 64 1

1 41 88

4 36 89 2

4 43 100 4

4 41 86 2

1 39 61

4 45 77 3

1 9 42

1 7 27

2 34 3

2 17 1

1 36 76

1 2 94

4 8 27 3

4 33 103 1

2 60 2

1 13 63

1 44 64

1 2 14

4 49 102 1

4 47 59 1

1 52 58

3 89

2 80 4

1 23 88

3 46

1 36 84

1 49 68

4 67 98 1

3 11

2 60 3

3 22

1 30 46

2 1 2

2 26 1

4 62 77 3

1 30 77

4 41 83 2

2 54 1

2 82 5

3 79

2 44 3

3 106

2 86 5

3 102

2 37 1

3 88

1 48 55

2 39 2

1 62 85

1 1 49

3 63

3 93

2 69 5

3 35

3 23

4 81 93 4

1 38 43

2 68 5

2 57 5

3 102

4 32 60 2

4 59 93 1

1 40 85

3 100

4 41 54 3

1 25 38

1 28 41

2 97 5

2 90 1

3 55

1 49 51

4 76 98 2

1 85 93

4 6 62 5

1 5 38

2 79 5

3 15

4 25 70 3

2 50 1

4 15 26 5

3 8

4 31 91 3

4 12 35 4

4 59 79 5

3 50

2 66 3

2 64 2

3 29

1 21 34

3 9

3 43

2 13 2

4 40 86 1

4 33 70 3

1 28 48

3 17

3 96

3 98

4 42 53 1

【样例输出】

9

9

9

7

3

16

12

2

10

1

8

4

5

8

4

1

13

11

4

13

6

7

9

10

3

【数据范围和约定】

对于100%的数据N<=250000,M<=250000,序列每个数在int范围之内且为正整数

对于10%的数据 N<=100 且和样例的输出一样

对于另外10%的数据 N,M<=5000

对于另外10%的数据 序列每个数<=3

对了另外30%的数据 N<=100000,每个数<=100000

而且出题人喜欢卡常数,所以请注意常数因子对程序的影响