CF1858E2 E2. Rollbacks (Hard Version)题解

E2. Rollbacks (Hard Version)

题目翻译

​ 初始有一个空的数组，我们需要对它进行q次操作，我们可以执行4种操作，操作+，添加一个元素x到数组后面。操作-，移除数组末尾的k个数字，操作！，撤回上一个操作，只会撤回+，-。操作？，输出数组种不同种类的数的个数。保证操作合法，hard版本要求强制在线。

思路

​ 首先本题我们看见其回退操作自然考虑使用可持久化的数据结构进行维护，考虑可持久化线段树，发现我们可以维护一个权值线段树表示每个值得元素是否有贡献，添加操作实际上就是新版本新建一个单点处理，减去操作实际上就是创建一个当前版本的k级祖先的镜像版本，回退操作实际上就是直接删去一个版本即可。考虑如何快速回调k级版本的祖先，我们可以维护倍增，记录每个版本的父亲版本倍增状态。但这样写完之后我们发现会MLE，经过计算我们发现我们最多只有1.4e7的空间给可持久化线段树，这是不够的，考虑优化，我们只用标记某个值是否做了贡献，所以我们可以进行状态压缩，把所有长度为32的区间压缩到一个int里，这样我们线段树的值域范围可以/32，这样我们需要1.6e7的空间。我们发现还是不够，考虑从倍增上搞点空间出来，以时间换空间倍增数组只用维护到2 ^ 17即可，这样我们就可以多出2e6的空间，就可以通过本题。

​ 本题还有O（q）的解法，我们发现我们实际上可以维护当前数组的长度，每个数我们记录其最早出现的位置来做贡献，这样我们查询答案实际上相当于查询长度为len的前缀，我们可以同时维护长度为len的答案ans[len]即可，加的操作我们修改之前这个位置的数，删去贡献处理新加的数覆盖即可。减操作直接len -= k即可。这样我们就解决了没有回退操作的解法，考虑如何处理回退操作，我们可以用栈维护每个操作带来的影响，最后直接弹出栈里的操作恢复状态即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//O(qlgq) 可持久化线段树
int cnt = 0;    //记录可以使用的新节点
struct node{
    int ls;
    int rs;
    int val;
};
int root[1000001];
node tree[16500001];
int fa[1000001][15];
int depth[1000001];
//要开的空间数为n * lg(4 * n)

//核心操作
int update(int pre, int pl, int pr, int x){
    //构建一颗只有lgn个新节点的新线段树
    int rt = ++cnt;

    //std::cerr << pl << space << pr << space << cnt << std::endl;

    if(pl == pr){
        int now = x % 32;
        tree[rt].val = tree[pre].val;
        now = (now - 1 + 32) % 32;
        tree[rt].val |= (1 << now);
        return rt;
    }

    //将该节点的左右儿子初始化为和上一颗线段树一样
    tree[rt].ls = tree[pre].ls;
    tree[rt].rs = tree[pre].rs;
    int mid = (pl + pr) >> 1;
    if(pl < pr){
        if((x + 32 - 1) / 32 <= mid)
            tree[rt].ls = update(tree[pre].ls, pl, mid, x);
        else
            tree[rt].rs = update(tree[pre].rs, mid + 1, pr, x);
    }

    tree[rt].val = (pl == mid ? __builtin_popcount(tree[tree[rt].ls].val) : tree[tree[rt].ls].val)
         + (pr == mid + 1 ? __builtin_popcount(tree[tree[rt].rs].val) : tree[tree[rt].rs].val);

    return rt;
}

int query(int p, int pl, int pr, int x){
    if(pl == pr){
        int now = x % 32;
        now = (now - 1 + 32) % 32;
        return ((tree[p].val >> now) & 1);
    }
    int mid = (pl + pr) >> 1;
    if((x + 32 - 1) / 32 <= mid)
        return query(tree[p].ls, pl, mid, x);
    else
        return query(tree[p].rs, mid + 1, pr, x);
}

void solve(){
    int n = 1e6;
    int maxn = (1e6 + 32 - 1) / 32;
    int q;
    std::cin >> q;
    cnt = 0;

    auto getk = [&](int x, int k){
        k = std::min(depth[x], k);
        for(int i = 14; i >= 0; i--){
            while(k >= (1 << i)){
                k -= (1 << i);
                x = fa[x][i];
            }
        }
        return x;
    };

    int top = 1;
    int val;
    char op;
    int from;
    int father;
    int node;
    int i;
    int j;
    for(i = 1; i <= q; i++){

        std::cin >> op;
        if(op == '+'){
            std::cin >> val;
            root[top] = update(root[top - 1], 1, maxn, val);
            father = top - 1;
            node = top;
            fa[node][0] = father;
            depth[node] = depth[father] + 1;
            for(j = 1; j <= 14; j++){
                fa[node][j] = fa[fa[node][j - 1]][j - 1];
            }
            top += 1;
        }
        else if(op == '-'){
            std::cin >> val;
            from = getk(top - 1, val);
            root[top] = root[from];
            depth[top] = depth[from];

            for(j = 0; j <= 14; j++)
                fa[top][j] = fa[from][j];
            top += 1;
        }
        else if(op == '!'){
            top -= 1;
        }
        else if(op == '?'){
            std::cout << tree[root[top - 1]].val << std::endl;
        }

    }
}

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//O(q)
void solve(){
    int N = 1e6;
    std::vector<int> tm(N + 2, N + 1);  //记录每个值得最早出现得位置
    std::vector<int> con(N + 2, 0);     //记录位置i的数是否产生了贡献
    std::vector<int> ref(N + 2, 0);     //记录位置i的之前的数是什么
    std::vector<int> ans(N + 2, 0);     //记录此时长度为i的序列的答案
    int len = 0;


    int top = 0;
    std::vector<int> stk(N + 1, 0);
    std::vector<int> save0(N + 1, 0);   //for tm[val]
    std::vector<int> save1(N + 1, 0);   //for tm[ref[len]]
    std::vector<int> save2(N + 1, 0);   //fot ref
    std::vector<int> save3(N + 1, 0);   //for ans

    int q;
    std::cin >> q;
    for(int i = 1; i <= q; i++){
        char op;
        std::cin >> op;
        if(op == '+'){
            int val;
            std::cin >> val;
            top += 1;

            stk[top] = val;
            len = len + 1;

            save1[top] = tm[ref[len]];
            save0[top] = tm[val];

            if(tm[ref[len]] == len){
                con[len] = false;
                tm[ref[len]] = 0;   //将之前这个位置的最小出现位重置，这里不用考虑下一个相同元素，要么添加覆盖，要么回退
            }
            if(tm[val] == 0 || tm[val] >= len){
                //取消远处标记的标记的贡献
                con[tm[val]] = false;
                //重置最小的元素出现位置
                tm[val] = len;
                con[len] = true;
            }

            save2[top] = ref[len];
            ref[len] = val;

            save3[top] = ans[len];
            ans[len] = ans[len - 1] + con[len];
            
        }
        else if(op == '-'){
            top += 1;
            int val;
            std::cin >> val;
            len = len - val;
            stk[top] = -val;    
        }
        else if(op == '!'){
            if(stk[top] > 0){
                ans[len] = save3[top];
                ref[len] = save2[top];
                if(save0[top] == 0 || save0[top] >= len){
                    con[len] = false;
                    tm[stk[top]] = save0[top];
                    con[tm[stk[top]]] = true;
                }
                if(save1[top] == len){
                    con[len] = true;
                    tm[save2[top]] = len;
                }
                len -= 1;
            }
            else{
                len -= stk[top];
            }
            top -= 1;
        }
        else if(op == '?'){
            std::cout << ans[len] << std::endl;
        }

        //std::cerr << i << space << len << std::endl;
    }
}