#P3337. ORZJRY I

ORZJRY I

题目描述

Jry 要维护一个整数序列。下表中的每个例子都独立地从初始序列 5 2 6 3 1 4 开始。

操作 含义 示例操作 操作后的序列或查询结果
1 x val 在第 xx 个数后插入 val\mathrm{val}。x=0x=0 表示在序列开头插入。 1 2 7 5 2 7 6 3 1 4
2 x 删除第 xx 个数。 2 1 2 6 3 1 4
3 x y 翻转第 xx 到第 yy 个数。 3 3 5 5 2 1 3 6 4
4 x y k 把第 xx 到第 yy 个数构成的区间循环右移 kk 位。 4 1 6 1 4 5 2 6 3 1
5 x y val 将第 xx 到第 yy 个数分别加 val\mathrm{val}。 5 3 4 5 5 2 11 8 1 4
6 x y val 将第 xx 到第 yy 个数全部设为 val\mathrm{val}。 6 1 4 7 7 7 7 7 1 4
7 x y 查询第 xx 到第 yy 个数之和。 7 2 4 1111
8 x y 查询第 xx 到第 yy 个数中最大值与最小值之差。 8 1 3 44
9 x y val 查询第 xx 到第 yy 个数与 val\mathrm{val} 的最小绝对差。 9 2 4 5 11
10 x y k 查询第 xx 到第 yy 个数中第 kk 小的数,相同的数按出现次数计。 10 1 6 4 44
11 x y val 查询第 xx 到第 yy 个数中严格小于 val\mathrm{val} 的个数。 11 2 5 4 33

输入格式

从标准输入读取。第一行是初始序列长度 nn,第二行是初始序列的 nn 个整数。第三行是操作数 qq。接下来 qq 行,每行一个操作,格式见上表。

输出格式

向标准输出写入。每次操作 77 到 1111 输出一行一个整数,表示查询结果。

样例 1

6
5 2 6 3 1 4
15
7 2 4
8 1 3
9 2 4 5
10 1 6 4
11 2 5 4
6 1 4 7
8 1 4
5 3 4 5
2 1
1 2 8
3 3 5
4 1 5 2
9 2 5 4
10 3 6 4
11 1 6 100
11
4
1
4
3
0
3
12
6

数据范围与约定

n,q≤100000n,q\le100000,任意时刻数列中的数都在 [0,231−1][0,2^{31}-1] 内。记当前序列长度为 ss。

  • 操作 11 的位置满足 0≤x≤s0\le x\le s。操作 22 的位置满足 1≤x≤s1\le x\le s。
  • 涉及区间的操作均满足 1≤x≤y≤s1\le x\le y\le s。
  • 操作 44 满足 1≤k≤y−x1\le k\le y-x。操作 1010 满足 1≤k≤y−x+11\le k\le y-x+1,排名从 1 开始。原 PDF 此处下界写成 0,本版已按操作含义修正。
  • 所有带 val\mathrm{val} 的操作均满足 val>0\mathrm{val}>0。