P3919 [Template] Persistent Segment Tree 1 (Persistent Array)

Added a set of hack testdata on 2021-09-18 by @panyf. The title describes the problem. With a persistent array, many derived persistent features can be implemented (for example: persistent union-find/DSU).

As described, you need to maintain an array of length $ N $, supporting the following two operations: 1. Modify the value at some position on a certain historical version. 2. Access the value at some position on a certain historical version. In addition, each time you perform an operation, a new version is created. The version number equals the current operation index (starting from $ 1 $; version $ 0 $ is the initial array). For operation $ 2 $, a completely identical version is created without any changes. That is, the version generated by a query is a copy of the version that is being accessed.

The first line contains two positive integers $ N, M $, the array length and the number of operations. The second line contains $ N $ integers, the initial values of the array (denoted as $ a_i $, $ 1 \leq i \leq N $). Each of the next $ M $ lines contains $ 3 $ or $ 4 $ integers, representing one of the two operations (assume the current operation is the $ i $-th): 1. For operation $ 1 $, the format is `v 1 p c`, meaning: based on version $ v $, set $ a_p $ to $ c $. 2. For operation $ 2 $, the format is `v 2 p`, meaning: access the value of $ a_p $ in version $ v $. Note: the version that is duplicated must be $ v $.

Output several lines, each being the result of an operation $ 2 $, in order.

Constraints - For $ 30\% $ of the testdata, $ 1 \leq N, M \leq 10^3 $. - For $ 50\% $ of the testdata, $ 1 \leq N, M \leq 10^4 $. - For $ 70\% $ of the testdata, $ 1 \leq N, M \leq 10^5 $. - For $ 100\% $ of the testdata: - $ 1 \leq N, M \leq 10^6 $; - $ 1 \leq p \leq N $; - Suppose this is the $ x $-th operation, then $ 0 \leq v < x $; - $ -10^9 \leq a_i, c \leq 10^9 $. Sample Explanation After all operations, a total of $ 11 $ versions are generated, numbered $ 0 \sim 10 $, in order: Version $ 0 $: `59 46 14 87 41`. Version $ 1 $: `59 46 14 87 41`. Version $ 2 $: `14 46 14 87 41`. Version $ 3 $: `57 46 14 87 41`. Version $ 4 $: `88 46 14 87 41`. Version $ 5 $: `88 46 14 87 41`. Version $ 6 $: `59 46 14 87 41`. Version $ 7 $: `59 46 14 87 41`. Version $ 8 $: `88 46 14 87 41`. Version $ 9 $: `14 46 14 87 41`. Version $ 10 $: `59 46 14 87 91`. Translated by ChatGPT 5