# C

# 题目大意

一排有 $N$ 个格子（初始时全部是白色）
有 $Q$ 个查询，每个查询给出一个 $a_i$，你需要

• 翻转从左数，第 $a_i$ 个格子的颜色，之后，统计当前所有连续的黑色格子区间的数量

# 数据范围

• $1 \le N, Q \le 5 \times 10^5$

# 题解

注意，题目是翻转

• 如果是涂黑
  • 如果左边右边均没有，那答案就 $+1$
  • 如果只有一边有，答案不变
  • 如果两边都有，答案 $-1$
• 如果是涂白
  • 如果左边右边均没有，答案 $-1$
  • 如果左边右边都有 答案 $+1$
  • 如果只有一边有，答案不变
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

    void solve () { cin >> n >> q, a = vector<int>(n + 2); while (q--) { cin >> x; if (!a[x]) { if (a[x + 1] && a[x - 1]) res--; else if (!a[x + 1] && !a[x - 1]) res++; } else { if (!a[x + 1] && !a[x - 1]) res--; else if (a[x + 1] && a[x - 1]) res++; } a[x] = !a[x], cout << res << '\n'; } }

# D

# 题目大意

你有一台服务器和 $n$ 台电脑，他们都各自持有一个字符串，初始时，均为空
接下来有 $Q$ 个操作，每个操作是下面三种之一

1. 1 p ：将第 $p$ 台电脑的字符串用服务器字符串替代
2. 2 p s ：在第 $p$ 台电脑的字符串末尾追加字符串 $s$
3. 3 p ：将服务器字符串用第 $p$ 台电脑的字符串替换

请你输出所有操作后的，服务器字符串

# 数据范围

• $1 \le n,Q \le 2 \times 10^5$

# 题解

# rope 王朝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int n, q, op, p;
string s;
rope<char> res;
vector<rope<char>> a;

void solve () {
    cin >> n >> q, a = vector<rope<char>>(n + 1, rope<char>(""));

    while (q--) {
        cin >> op;
        if (op == 1)
            cin >> p, a[p] = res;
        else if (op == 2)
            cin >> p >> s, a[p] += rope<char>(s.c_str());
        else
            cin >> p, res = a[p];
    }

    for (int i = 0; i < res.size(); i++)
        cout << res[i];
}

# 递归解法

定义一个这样的结构， pair<int, string>: <上一版本的结点编号，添加的字符串>

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

void dfs(int u) {
    if (u == -1)
        return;

    dfs(v[u].first);
    cout << v[u].second;
}

void solve () {
    cin >> n >> q, idx = vector<int>(n + 1);

    for (int i = 0; i < n; i++)
        idx[i] = i, v.push_back({-1, ""});

    while (q--) {
        cin >> op;
        
        if (op == 1)
            cin >> p, v.push_back({idx[0], ""}), idx[p] = v.size() - 1;
        else if (op == 2)
            cin >> p >> s, v.push_back({idx[p], s}), idx[p] = v.size() - 1;
        else
            cin >> p, v.push_back({idx[p], ""}), idx[0] = v.size() - 1;
    }

    dfs(idx[0]);
}