CF1117G Recursive Queries

发表于 更新于

标签

笛卡尔树 + 树状数组 + 线段树

思路

真是道笛卡尔树好题！

这个题显然问的是 [l,r][l, r] 构成的笛卡尔树每个节点的大小和。等于每个节点的深度和。事实上大小和，深度和都能做这道题，不过我写了深度和。

暴力建笛卡尔树是 O(nq)O(nq)​ 的，过不去。考虑笛卡尔树的构建过程。可以用树状数组区间加，区间求和。来维护每个点的深度。

因为笛卡尔树的构建是插入式的，所以当插入到第 ii 个数时，笛卡尔树上恰好有 [1,i][1, i], 根据 f(l,r)=(r−l+1)+f(l,ml,r−1)+f(ml,r+1,r)f(l, r) = (r - l + 1) + f(l, m_{l, r} - 1) + f(m_{l, r} + 1, r) ，考虑把 f(l,r)f(l, r) 分成 f(l,ml,r+1)f(l, m_{l,r} + 1) 和 f(ml,r+1,r)f(m_{l, r} + 1, r) 来求，这样的好处是 ml,rm_{l, r} 有更多的性质，也就意味它在笛卡尔树上更容易找到。

至于寻找 ml,rm_{l, r}​ 的方法，根据笛卡尔树的构建过程，构建笛卡尔树时栈里的点为从根一直走右儿子走到当前点所经过的所有的点。因为 ml,rm_{l, r} 为 [l,r][l, r] 内最大的点，所以 ml,rm_{l, r} 一定在栈内。在栈内二分找到第一个 ≥l\geq l 的点即可，然后求区间和.

关于 ml,rm_{l,r} 在栈内的证明 :

假设 ml,rm_{l, r} 不在栈内，那它可以通过跳父亲一直跳到右链，它跳到的点无论下标还是权值都一定比它大，不符合 ml,rm_{l, r} 是 [l,r][l, r] 内最大的点.

求 f(l,ml,r+1)f(l, m_{l, r} + 1) 和 f(ml,r+1,r)f(m_{l, r} + 1, r) 的方法是对称的，会求其中一个另一个也就会了

Code

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <vector>
#include <set>
#define int long long
 
using namespace std;
 
const int N = 1e6 + 10;
int n, m;
int val1[N], val2[N];
int a[N];
int q[N], top;
vector<pair<int, int> > l[N];
 
int lowbit(int x) {
    return x & (-x);
}
 
void change(int x, int y, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        val1[i] += v, val2[i] += v * x;
    }
    for (int i = y + 1; i <= n; i += lowbit(i)) {
        val1[i] -= v, val2[i] -= v * (y + 1);
    }
}
 
int query(int x, int y) {
    if (x > y) return 0;
    int res = 0;
    for (int i = y; i; i -= lowbit(i)) {
        res -= val2[i], res += val1[i] * (y + 1);
    }
    for (int i = x - 1; i; i -= lowbit(i)) {
        res += val2[i], res -= val1[i] * (x);
    }
    return res;
}
int ans[N];
int x[N], y[N];
 
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%lld", &x[i]);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%lld", &y[i]);
        ans[i] = y[i] - x[i] + 1;
    }
    for (int i = 1; i <= m; ++i) {
        l[y[i]].push_back(make_pair(x[i], i));
    }
    for (int i = 1; i <= n; ++i) {
        int las = 0, fir = 0;
        fir = q[top];
        while (top && a[i] > a[q[top]]) las = q[--top];
        if (top) change(i, i, query(q[top], q[top]) + 1);
        else change(i, i, 1);
        if (fir != las) {
            change(q[top] + 1, i - 1, 1);
        }
        q[++top] = i;
        for (auto it : l[i]) {
            int w = *lower_bound(q + 1, q + top + 1, it.first);
            ans[it.second] += query(w + 1, i) - (i - w) * query(w, w);
        }
    }
    top = 0;
    for (int i = 1; i <= n; ++i) {
        val1[i] = val2[i] = 0;
    }
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= m; ++i) {
        swap(x[i], y[i]);
        x[i] = n - x[i] + 1;
        y[i] = n - y[i] + 1;
    }
    for (int i = 1; i <= n; ++i) {
        l[i].clear();
    }
    for (int i = 1; i <= m; ++i) {
        l[y[i]].push_back(make_pair(x[i], i));
    }
    for (int i = 1; i <= n; ++i) {
        int las = 0, fir = 0;
        fir = q[top];
        while (top && a[i] > a[q[top]]) las = q[--top];
        if (top) change(i, i, query(q[top], q[top]) + 1);
        else change(i, i, 1);
        if (fir != las) {
            change(q[top] + 1, i - 1, 1);
        }
        q[++top] = i;
        for (auto it : l[i]) {
            int w = *lower_bound(q + 1, q + top + 1, it.first);
            ans[it.second] += query(w + 1, i) - (i - w) * query(w, w);
        }
    }
    for (int i = 1; i <= m; ++i) {
        printf("%lld ", ans[i]);
    }
    return 0;
}