题解：CF2201A2 Lost Civilization (Hard Version)

· · 题解

C1/C2

题解

Part.1

模拟样例可以发现，最终的序列是多个树形结构。在操作过程中，在 x 后插入 x'，就在其之间连边，最后，原始序列中的每一个元素都恰好对应一个树，且每棵树恰好对应结果序列中的一个区间（每次都紧贴着插入，扩展时不会跨过其他元素），原始序列中的每一个元素对应的区间不相交，且区间内的顺序就是树的 DFS 序。所以，我们可以用 DFS 遍历每一棵树，找到每个树对应区间的范围，再遍历下一颗树。答案就是树的数量。

Part.2

画图模拟样例可以发现，若创建一个源点，向每个树根连边，则区间 [l, r] 的答案就是 [dfn_l, dfn_r] 内的前缀深度最小值的数量（重复出现也算）。但这样再怎么做也要 O(n^2)。对于求和，计数类问题，一般都可以考虑拆贡献（思考 45 min 才想到拆贡献的事）。对于 dfn 上一个节点 x，他会对询问区间左端点 l 造成贡献当且仅当他们之间没有深度小于 x 的点，且会直接贡献 n - x + 1，因为右端点只要包括 x 就行。所以用单调栈找到最小的 y 并用差分维护就行。时间 O(n)。

启示

Code

应该比较简洁了吧。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 5;

ll T, n, cnt, ans;
ll a[N], deep[N], b[N], f[N];
stack<int> stk;

void DFS(int &p, int val, int dep) {
    deep[p] = dep;
    for (p++; a[p] == val + 1; ) {
        DFS(p, val + 1, dep + 1);
    }
    return ;
}

void Clear() {
    cnt = ans = 0;
    for (int i = 0; i <= n + 1; i++) {
        a[i] = deep[i] = b[i] = f[i] = 0;
    }
    for (; !stk.empty(); stk.pop()) ; 
    return ;
}

void Solve() {
    Clear();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int p = 1; p <= n; ) {
        cnt++;
        DFS(p, a[p], 1);
    }
    for (int i = 1; i <= n; i++) {
        for (; !stk.empty() && deep[stk.top()] >= deep[i]; stk.pop()) ;
        if (!stk.empty()) {
            f[i] = stk.top();
        }
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) {
        b[f[i] + 1] += n - i + 1;
        b[i + 1] -= n - i + 1;
    }
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        ans += b[i];
    }
    cout << ans << '\n';
    return ;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (cin >> T; T--; Solve()) ;
    return 0;
}