Description

主席树就是可持久化线段树。所谓“可持久化”的数据结构并非指将数据存在非易失的存储器上，而是指保存了数据修改的历史信息。比如说对可持久化线段树进行修改操作，操作完成后我们可以在线段树原有的时间复杂度内查询到希望查询的版本的信息，比如“第二次修改后区间L和R之间的和”。通常遇到的线段树都是构建之后结构不变化的，所以在修改关键值时，只有节点内的值受到影响，而树本身的结构不发生变化（比如左右子节点所表示的区间）。这为线段树进行可持久化提供了便利。我们每次修改的时候不直接改动原来节点的值，而是创建一系列新的节点。如果整棵树复制的话不仅非常耗费时间，而且占用空间太大。在线段树的单次修改中，实际上受到影响的节点是有限的，原来的节点可以得到重复利用。可持久化线段树每次修改都会自上而下地新建一些节点。每次修改后的版本都有一个根节点与之对应。只考虑单点修改，我们将递归过程中所有的节点创建一个“影子节点”，所谓“影子节点”保存的是当前修改结束后的受到更改的值。当u是v的影子节点时，我们称v时u的原节点。在线段树的修改操作中，子节点修改完成后只影响到父节点（pushup操作），而不会影响到兄弟节点。所以我们发现，当修改影响到非叶子结点u时，（在单点修改中）他一定只有一个子节点会受到修改的影响，比如右子节点受到影响，此时u的影子节点v的左子节点指向u的左子节点，而v的右子节点对应的是受到影响的新右子节点w，w是u的右子节点的影子节点，以此类推。对于区间修改，需要维护一个lazy标签来推迟更新操作，在pushdown操作时，创建了u的原节点的子节点的影子节点，在实际实现中，通过维护一个节点的origin节点指针就可以做到这一点。因为这个东西太难了。对于本题，我们要化简题目难度。无论任何输入数据，你需要回答的是，什么是主席树？

Input Format

第一行包含两个整数N和M。

第二行包含N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

数据范围：1≤N,M≤10^5, |d|≤10000, |A[i]|≤1000000000

Output Format

求出答案

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2​

可持久化线段树​

Source

新年赛