Kingdom of Criticism

题意翻译

你正在写一道小清新数据结构题，突然 |x| 进来了，于是你假装在打 galgame: 你需要维护一个长度为 $n$ 的序列，支持以下三个操作： 1. `1 k w`：单点修改。 2. `2 k`：单点查询。 1. `3 l r`：对整个区间中值 $\in[l,r]$ 的，将其修改为 $l-1$ 与 $r+1$ 中离他更近的那一个。保证 $r-l$ 为奇数。 注：如果后面的操作与前面的矛盾，不管前面的。 数据范围：$1\leq n,q\leq 4\times 10^5$。 translated by |x|

题目描述

Pak Chanek is visiting a kingdom that earned a nickname "Kingdom of Criticism" because of how often its residents criticise each aspect of the kingdom. One aspect that is often criticised is the heights of the buildings. The kingdom has $ N $ buildings. Initially, building $ i $ has a height of $ A_i $ units. At any point in time, the residents can give a new criticism, namely they currently do not like buildings with heights between $ l $ and $ r $ units inclusive for some two integers $ l $ and $ r $ . It is known that $ r-l $ is always odd. In $ 1 $ minute, the kingdom's construction team can increase or decrease the height of any building by $ 1 $ unit as long as the height still becomes a positive number. Each time they receive the current criticism from the residents, the kingdom's construction team makes it so that there are no buildings with heights between $ l $ and $ r $ units inclusive in the minimum time possible. It can be obtained that there is only one way to do this. Note that the construction team only cares about the current criticism from the residents. All previous criticisms are forgotten. There will be $ Q $ queries that you must solve. Each query is one of the three following possibilities: - 1 k w: The kingdom's construction team changes the height of building $ k $ to be $ w $ units ( $ 1 \leq k \leq N $ , $ 1 \leq w \leq 10^9 $ ). - 2 k: The kingdom's construction team wants you to find the height of building $ k $ ( $ 1 \leq k \leq N $ ). - 3 l r: The residents currently do not like buildings with heights between $ l $ and $ r $ units inclusive ( $ 2 \leq l \leq r \leq 10^9-1 $ , $ r-l $ is odd). Note that each change in height still persists to the next queries.

输入输出格式

输入格式

The first line contains a single integer $ N $ ( $ 1 \leq N \leq 4 \cdot 10^5 $ ) — the number buildings in the kingdom. The second line contains $ N $ integers $ A_1, A_2, \ldots, A_N $ ( $ 1 \leq A_i \leq 10^9 $ ) — the initial heights of the buildings. The next line contains a single integer $ Q $ ( $ 1 \leq Q \leq 4 \cdot 10^5 $ ) — the number of queries. The $ j $ -th of the next $ Q $ lines contains the $ j $ -th query as described. There is at least one query of type $ 2 $ .

输出格式

For each query of type $ 2 $ , output a line containing an integer representing the height of the building asked.

输入输出样例

输入样例 #1

5
2 6 5 6 2
9
1 5 10
2 5
1 1 3
3 3 6
3 8 9
1 2 9
2 3
2 2
2 4

输出样例 #1

10
7
9
7

说明

After the $ 1 $ -st query, the height of each building is $ 2, 6, 5, 6, 10 $ . After the $ 3 $ -rd query, the height of each building is $ 3, 6, 5, 6, 10 $ . After the $ 4 $ -th query, the height of each building is $ 2, 7, 7, 7, 10 $ . After the $ 5 $ -th query, the height of each building is $ 2, 7, 7, 7, 10 $ . After the $ 6 $ -th query, the height of each building is $ 2, 9, 7, 7, 10 $ .

**题目大意：**

你正在访问一个名为“批评王国”的王国，因为那里的居民经常批评王国的各个方面。经常被批评的一个方面是建筑物的高度。王国里有 $ N $ 栋建筑，最初，建筑 $ i $ 的高度为 $ A_i $ 单位。

任何时候，居民都可能提出新的批评，即他们目前不喜欢高度在 $ l $ 和 $ r $ 之间的建筑（包括 $ l $ 和 $ r $）。已知 $ r-l $ 总是奇数。

王国建筑团队每分钟可以增加或减少任何建筑的高度 $ 1 $ 单位，只要高度仍然是正数。每次他们接到居民的当前批评，王国的建筑团队就会尽可能快地使不存在高度在 $ l $ 和 $ r $ 之间的建筑。可以得知只有一种方法可以做到这一点。

注意，建筑团队只关心居民当前的批评。所有先前的批评都被遗忘了。

你必须解决 $ Q $ 个查询。每个查询是以下三种可能性之一：

- `1 k w`：王国的建筑团队将建筑 $ k $ 的高度更改为 $ w $ 单位（$ 1 \leq k \leq N $，$ 1 \leq w \leq 10^9 $）。
- `2 k`：王国的建筑团队希望你找到建筑 $ k $ 的高度（$ 1 \leq k \leq N $）。
- `3 l r`：居民目前不喜欢高度在 $ l $ 和 $ r $ 之间的建筑（$ 2 \leq l \leq r \leq 10^9-1 $，$ r-l $ 是奇数）。

注意，高度的变化会持续到下一个查询。

**输入输出格式：**

**输入格式：**

第一行包含一个整数 $ N $（$ 1 \leq N \leq 4 \times 10^5 $）——王国的建筑数量。

第二行包含 $ N $ 个整数 $ A_1, A_2, \ldots, A_N $（$ 1 \leq A_i \leq 10^9 $）——建筑的初始高度。

下一行包含一个整数 $ Q $（$ 1 \leq Q \leq 4 \times 10^5 $）——查询的数量。

接下来的 $ Q $ 行中的第 $ j $ 行包含第 $ j $ 个查询的描述。至少有一个类型为 $ 2 $ 的查询。

**输出格式：**

对于每个类型为 $ 2 $ 的查询，输出一行，包含一个整数，表示所询问的建筑的高度。

**输入输出样例：**

**输入样例 #1：**

```
5
2 6 5 6 2
9
1 5 10
2 5
1 1 3
3 3 6
3 8 9
1 2 9
2 3
2 2
2 4
```

**输出样例 #1：**

```
10
7
9
7
```**题目大意：** 你正在访问一个名为“批评王国”的王国，因为那里的居民经常批评王国的各个方面。经常被批评的一个方面是建筑物的高度。王国里有 $ N $ 栋建筑，最初，建筑 $ i $ 的高度为 $ A_i $ 单位。 任何时候，居民都可能提出新的批评，即他们目前不喜欢高度在 $ l $ 和 $ r $ 之间的建筑（包括 $ l $ 和 $ r $）。已知 $ r-l $ 总是奇数。 王国建筑团队每分钟可以增加或减少任何建筑的高度 $ 1 $ 单位，只要高度仍然是正数。每次他们接到居民的当前批评，王国的建筑团队就会尽可能快地使不存在高度在 $ l $ 和 $ r $ 之间的建筑。可以得知只有一种方法可以做到这一点。 注意，建筑团队只关心居民当前的批评。所有先前的批评都被遗忘了。 你必须解决 $ Q $ 个查询。每个查询是以下三种可能性之一： - `1 k w`：王国的建筑团队将建筑 $ k $ 的高度更改为 $ w $ 单位（$ 1 \leq k \leq N $，$ 1 \leq w \leq 10^9 $）。 - `2 k`：王国的建筑团队希望你找到建筑 $ k $ 的高度（$ 1 \leq k \leq N $）。 - `3 l r`：居民目前不喜欢高度在 $ l $ 和 $ r $ 之间的建筑（$ 2 \leq l \leq r \leq 10^9-1 $，$ r-l $ 是奇数）。 注意，高度的变化会持续到下一个查询。 **输入输出格式：** **输入格式：** 第一行包含一个整数 $ N $（$ 1 \leq N \leq 4 \times 10^5 $）——王国的建筑数量。 第二行包含 $ N $ 个整数 $ A_1, A_2, \ldots, A_N $（$ 1 \leq A_i \leq 10^9 $）——建筑的初始高度。 下一行包含一个整数 $ Q $（$ 1 \leq Q \leq 4 \times 10^5 $）——查询的数量。 接下来的 $ Q $ 行中的第 $ j $ 行包含第 $ j $ 个查询的描述。至少有一个类型为 $ 2 $ 的查询。 **输出格式：** 对于每个类型为 $ 2 $ 的查询，输出一行，包含一个整数，表示所询问的建筑的高度。 **输入输出样例：** **输入样例 #1：** ``` 5 2 6 5 6 2 9 1 5 10 2 5 1 1 3 3 3 6 3 8 9 1 2 9 2 3 2 2 2 4 ``` **输出样例 #1：** ``` 10 7 9 7 ```