P1383 高级打字机 主席树

传送门：https://www.luogu.com.cn/problem/P1383

Problem Description

超级简单的模板题

与普通的主席树相比，这个题查询的不是第 k k k大，但是查询思路跟查询第 k k k大的思路相似。

对于插入操作，我们每次新建一棵主席树，然后树上左右递归到叶节点将其权值赋为 1 1 1，同时记录这个权值点映射的字母。

对于查询操作，跟主席树思路类似，每个点储存子树节点的数量，这样左右二分可以得到答案。

对于撤销操作，这里虽然是撤销，但我们仍然新建根节点，但是这里不需要更新，直接将前第 n o w s t e p − t − 1 nowstep - t - 1 nowstep−t−1步的 r o o t root root拷贝到新节点就可以了。

大致结构跟普通主席树几乎一致，就是多了个顺序映射，以及权值数组只表示先后顺序不表示大小顺序。

Accepted Code

#include 
using namespace std;

const int N = 1e6 + 10;

int sum[N > n;
    for(int i = 1; i > tem;
            ++cnt;
            root[cnt] = root[cnt - tem - 1];
        }
        else if(op == 'Q'){
            int tem; cin >> tem;
            cout