笛卡尔树

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
struct DKR {
    int n;
    vector<int> l, r;
    int root;
    stack<int> st;

    DKR(int nn) : n(nn), l(nn + 1), r(nn + 1), root(0) {}
    // 默认为小根堆，维护最小值所在区间
    // dkr.built(a,less<int>());大根堆
    int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) {
        while (!st.empty()) st.pop();  // 清空栈
        for (int i = 1; i <= n; i++) {
            int last = 0;

            while (!st.empty() && cmp(a[st.top()], a[i])) {
                last = st.top();
                st.pop();
            }
            if (!st.empty()) {
                r[st.top()] = i;
            } else {
                root = i;
            }
            l[i] = last;
            st.push(i);
        }
        return root;
    }
};

给定一个 1∼n1 \sim n 的排列 pp，构建其笛卡尔树。

即构建一棵二叉树，满足：

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 ii 的权值为 pip_i，每个节点的权值满足小根堆的性质。

设 li,ril_i,r_i 分别表示节点 ii 的左右儿子的编号（若不存在则为 00）。

一行两个整数，分别表示 xor⁡i=1ni×(li+1)\operatorname{xor}_{i = 1}^n i \times (l_i + 1) 和 xor⁡i=1ni×(ri+1)\operatorname{xor}_{i = 1}^n i \times (r_i + 1)。

这是一种数据结构，可以把一堆形如 (xi,yi) 的点对放到二叉树上，使得：

  • 只看 x，树的中序遍历有序，即满足二叉搜索树（Binary Search Tree, BST）性质（左小右大）
  • 只看 y，这是一个二叉堆，大根/小根堆

它的性质非常优秀，可以支持一些跟最大值有关的问题，或者是插入删除之类的问题（记录插入删除时间）

建树：发现左子树的结构不会改变，维护最右链的单调栈。每次找到位置后，将原先剩余右边子树接到新点的左子树。注意维护root,，就是 a[i]一来直接变成当前最小值，反 客 为 主，此时不但要清掉链，还要把根设置成 (i,a[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    DKR dkr(n);
    dkr.built(a);;
    ll ans1=0, ans2 = 0;
    for (int i = 1; i <= n; i++) {
        ans1 ^= (ll)i * (dkr.l[i] + 1);
        ans2 ^= (ll)i * (dkr.r[i] + 1);
    }
    cout << ans1 << " " << ans2 << endl;
}

性质 / 事实

（以小根为例）

  1. 以 u 为根的子树是一段连续的区间 （由BST性质），且u 是这段区间的最小值，且不能再向两端延伸使得最小值不变（即，这一段区间是极长的）

  2. 在 u左右子树里任选两个点，两点间的区间最小值必定是$ y_{u}$

    注：两个点都可以取 u 本身，此时的区间最小值仍是$ y_{u}$

  3. a,b 间的区间最小值为:yLCA(a,b)y_{LCA(a,b)}

  4. 若 y 是个随机排列，x是 1,2,3…n,则树高期望为 log

  5. Treap是一颗笛卡尔树，它依靠性质4确保复杂度

    ——因此我们可以动态维护笛卡尔树！

[TJOI2011] 树的序

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：

  1. 空树中加入一个键值 kk，则变为只有一个结点的二叉查找树，此结点的键值即为 kk。
  2. 在非空树中插入一个键值 kk，若 kk 小于其根的键值，则在其左子树中插入 kk，否则在其右子树中插入 kk。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个.

Sol:发现a[i]满足BST的key，而二叉树后来的下标一定在先来的下面符合小根堆。以(a[i],i)建笛卡尔树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[x] = i;
    }
    DKR dkr(n);
    dkr.built(a);
    vector<int> ans(n + 1);
    int tot = 0;
    auto dfs = [&](auto self, int u) -> void {
        ans[++tot] = u;
        if (dkr.l[u])
            self(self, dkr.l[u]);
        if (dkr.r[u])
            self(self, dkr.r[u]);
    };
    dfs(dfs, dkr.root);
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}

随机数据下1e7级别的RMQ

主要问题ST表在于空间开不下，考虑笛卡尔树建立，但是不能求lca，空间依然不够。考虑随机数据下笛卡尔树的树高不超过logn,所以考虑直接从根暴力寻找。

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
int a[N], l[N], r[N];
int built(int n) {
    stack<int> st;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int last = 0;
        while (!st.empty() && a[st.top()] < a[i]) {
            last = st.top();
            st.pop();
        }
        if (!st.empty())
            r[st.top()] = i;
        else
            root = i;
        l[i] = last;
        st.push(i);
    }
    return root;
}  // dfs(root);
void solve() {
    int n, m, s;
    cin >> n >> m >> s;
    srand(s);
    ull ans = 0;
    for (int i = 1; i <= n; i++) a[i] = read();
    int root = built(n);
    for (int i = 1; i <= m; i++) {
        int tl, tr;
        tl = read() % n + 1, tr = read() % n + 1;
        int ql = min(tl, tr), qr = max(tl, tr);
        // 树高期望log
        int cur = root;
        while (cur < ql || cur > qr) {
            if (cur < ql)
                cur = r[cur];
            else
                cur = l[cur];
        }
        ans += a[cur];
    }
    cout << ans << endl;
}

笛卡尔树实现维护单调栈基本功能：左边第一个大的数，右边第一个大的数

对于给定由 n 个元素构成的数组。一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。https://www.luogu.com.cn/problem/CF817D

Sol:求∑l=1n∑r=ln(max⁡i=lr{ai}−min⁡i=lr{ai})\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r\{a_i\}-\min_{i=l}^r\{a_i\}\right)，考虑两部分拆式子

等价于求∑l=1n∑r=ln(max⁡i=lr{ai}−min⁡i=lr{ai})=∑l=1n∑r=lnmax⁡i=lr{ai}−∑l=1n∑r=lnmin⁡i=lr{ai}\begin{aligned} \sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r\{a_i\}-\min_{i=l}^r\{a_i\}\right)=\sum_{l=1}^n\sum_{r=l}^n\max_{i=l}^r\{a_i\}-\sum_{l=1}^n\sum_{r=l}^n\min_{i=l}^r\{a_i\} \end{aligned}

再考虑贡献法，a[i]作为最大值的极长区间是从哪到哪，则知道了a[i]在多少个区间作为最大值，就是贡献多少次。最小值同理

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
struct DKR {
    int n;
    vector<int> ls, rs;
    int root;
    stack<int> st;
    vector<int> nxt, pre;  // 极长最左边的下标，最右边的下标
    DKR(int nn) {
        n = nn;
        ls.resize(n + 1);
        rs.resize(n + 1);
        root = 0;
        nxt.resize(n + 1);
        pre.resize(n + 1);
    }
    // 默认为小根堆，维护最小值所在区间
    // dkr.built(a,less<int>());大根堆
    int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) {
        while (!st.empty()) st.pop();  // 清空栈
        for (int i = 1; i <= n; i++) {
            int last = 0;
            while (!st.empty() && cmp(a[st.top()], a[i])) {
                last = st.top();
                st.pop();
            }
            if (!st.empty()) {
                rs[st.top()] = i;
            } else {
                root = i;
            }
            ls[i] = last;
            st.push(i);
        }
        return root;
    }
    void dfs(int u) {
        nxt[u] = pre[u] = u;
        deb(u, ls[u], rs[u]);

        if (ls[u]) {
            dfs(ls[u]);
            nxt[u] = max(nxt[u], nxt[ls[u]]);
            pre[u] = min(pre[u], pre[ls[u]]);
        }
        if (rs[u]) {
            dfs(rs[u]);
            nxt[u] = max(nxt[u], nxt[rs[u]]);
            pre[u] = min(pre[u], pre[rs[u]]);
        }
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    DKR dmn(n), dmx(n);
    dmn.built(a);
    dmx.built(a, less<int>());
    dmn.dfs(dmn.root);
    dmx.dfs(dmx.root);
    ll mx = 0, mn = 0;
    for (int i = 1; i <= n; i++) {
        ll len = (ll)max(1, i - dmn.pre[i] + 1) * max(1, (dmn.nxt[i] - (i) + 1));
        mn += (ll)len * a[i];
        ll len1 = (ll)max(1, i - dmx.pre[i] + 1) * max(1, (dmx.nxt[i] - (i) + 1));
        mx += (ll)len1 * a[i];
    }
    cout << mx - mn << endl;
}