RenaMoe's Blog

念念不忘，必有回响

0%

题解 CF1117G Recursive Queries

发表于 分类于 ， Valine：

给出一个长为 n 的排列，每次给出询问 \([l_i,r_i]\)（可以离线），求 \(f(l_i,r_i)\)： \[ f(l,r)=\begin{cases} (r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)\quad &(l\le r)\\ 0\quad &(l > r) \end{cases} \]

\(m_{l,r}\) 为 \([l,r]\) 的最大值的位置。

思路

转化题意

给出的式子应该很好理解吧，就是区间最大值将区间分开，递归下去。

那么一个区间的最大值也就代表这个区间，其贡献为区间长度。

最后该区间的答案就是每个点的贡献之和。

设 i 左边第一个大于 \(a_i\) 的位置为 \(lb(i)\)，右边第一个大于 \(a_i\) 的位置为 \(rb(i)\)，（若无该位置，\(lb(i)=0,rb(i)=n+1\)）。

其实就是要统计：

\[ \sum_{i=l}^r\min(rb(i)-1,r)-\max(lb(i)+1,l)+1 \]

预处理 \(lb(i),rb(i)\)

利用单调栈 \(O(n)\) 处理即可。

1
2
3
4
5
6
7
8
int top = 0;
for (int i = 1; i <= n; ++i) {
    while (top && a[stk[top]] < a[i])
        rb[stk[top--]] = i;
    lb[i] = stk[top];
    stk[++top] = i;
}
while (top) rb[stk[top--]] = n + 1;

离线统计

现将每个点的贡献拆开，分别统计 \(lb(i),rb(i)\)，需要区间求和。

以统计 \(lb(i)\) 为例：

注意到如果 \(i\in [l,r],lb(i)+1<l\)，该点贡献为 \(l\)。

我们将所有询问离线下来，固定 l，对每个 r 区间求和。

每次向右移动 l，所有 \(lb(i)=l\) 的位置的贡献都应该改为 l。

那么就把这些位置去掉贡献，打上 tag，每次统计答案时，统计区间有 tag 的个数另外计算。

单点修改，区间查询，开两棵树状数组分别维护 \(lb(i)\) 的贡献和 tag 个数。

统计 \(rb(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
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
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

namespace RenaMoe {
template <typename TT> inline void read(TT &x) {}

typedef long long LL;
const int N = 1e6 + 9;

struct Ask {
    int l, r;
};

int n, m;
int a[N], lb[N], rb[N], stk[N];
LL ans[N];
Ask q[N];
vector<int> qry[N], del[N]; // qry[i]：左端点为i的询问，del[i]：lb为i的位置

struct Bit {
    LL tr[N];
    inline void clear() {
        memset(tr, 0, sizeof tr);
    }
    inline void update(int x, LL k) {
        for (int i = x; i <= n; i += i & -i)
            tr[i] += k;
    }
    inline LL query(int x) {
        LL re = 0;
        for (int i = x; i; i -= i & -i)
            re += tr[i];
        return re;
    }
} tr1, tr2;

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) read(q[i].l);
    for (int i = 1; i <= m; ++i) read(q[i].r);
    
    // 单调栈求lb[i],rb[i]
    int top = 0;
    for (int i = 1; i <= n; ++i) {
        while (top && a[stk[top]] < a[i])
            rb[stk[top--]] = i;
        if (top) lb[i] = stk[top];
        stk[++top] = i;
    }
    while (top) rb[stk[top--]] = n + 1;

    for (int i = 1; i <= n; ++i)
        del[lb[i]].push_back(i);
    for (int i = 1; i <= m; ++i)
        qry[q[i].l].push_back(i);
    for (int i = 1; i <= n; ++i)
        tr1.update(i, lb[i]); // 注意+1-1的细节
    for (int i = 1; i <= n; ++i) {
        // 清除贡献，打tag
        for (int j = 0; j < del[i-1].size(); ++j) {
            tr1.update(del[i-1][j], -lb[del[i-1][j]]);
            tr2.update(del[i-1][j], 1);
        }
        for (int j = 0; j < qry[i].size(); ++j) {
            int id = qry[i][j];
            ans[id] -= tr1.query(q[id].r) - tr1.query(q[id].l-1);
            ans[id] -= (LL)(i - 1) * (tr2.query(q[id].r) - tr2.query(q[id].l-1));
        }
    }
    
    for (int i = 0; i <= n; ++i)
        del[i].clear(), qry[i].clear();
    for (int i = 1; i <= n; ++i)
        del[rb[i]].push_back(i);
    for (int i = 1; i <= m; ++i)
        qry[q[i].r].push_back(i);
    tr1.clear(), tr2.clear();
    for (int i = 1; i <= n; ++i)
        tr1.update(i, rb[i]-1);
    for (int i = n; i; --i) {
        for (int j = 0; j < del[i+1].size(); ++j) {
            tr1.update(del[i+1][j], -rb[del[i+1][j]]+1);
            tr2.update(del[i+1][j], 1);
        }
        for (int j = 0; j < qry[i].size(); ++j) {
            int id = qry[i][j];
            ans[id] += tr1.query(q[id].r) - tr1.query(q[id].l-1);
            ans[id] += (LL)i * (tr2.query(q[id].r) - tr2.query(q[id].l-1));
        }
    }

    for (int i = 1; i <= m; ++i)
        printf("%lld ", ans[i]);
    puts("");
    return 0;
}