DDOSvoid's Blog

CF 1117G Recursive Queries

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/1117/G

简要题意：给定一个长度为 $n$ 的排列 $p$，还有 $m$ 次询问，每次询问给定 $l,r$，求 $f(l,r)$，其中 $f(l,r)=(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)$，$m_{l,r}$ 表示 $[l,r]$ 中的最大值的位置，对于 $l>r$ 的情况，$f(l,r)=0$

$n,m\le 10^6$

Solution

令 $L_i$ 表示第一个左边大于 $p_i$ 的位置，$R_i$ 表示右边第一个大于 $p_i$ 位置，容易得到答案就是 $\sum_{i=l}^r min(R_i-1,r)-max(L_i+1,l)+1$

有一种非常 $trivial$ 的做法，我们建一棵主席树，然后 $min(R_i-1,r)$ 相当于查询小于 $r$ 的 $R_i-1$ 的和，以及大于 $r$ 的 $R_i-1$ 的个数，$L_i+1$ 同理，这样常数比较大

注意到我们一次询问相当于只需要 $[l,r]$ 中的数的贡献，我们将这个东西差分一下，尝试维护前缀的贡献

那么相当于我们每次区间 $[L_i+1,R_i-1]$ 区间加 $1$，然后查询只需要查询 $[l,r]$ 的和即可

区间加区间查询可以用树状数组实现，时间复杂度 $O(n\log n)$

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#define maxn 1000010
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int n, m, a[maxn], l[maxn], r[maxn];
pair<int, int> Q[maxn];

struct Fenwick {
    ll B1[maxn], B2[maxn];
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += x * v;
    }

    ll get_sum(int x) {
        ll s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += (x + 1) * B1[i], s -= B2[i];
        return s; 
    }

    void update(int l, int r, int v) { add(l, v); add(r + 1, -v); }

    ll query(int l, int r) { return get_sum(r) - get_sum(l - 1); } 
} Bit;

struct node {
    int type, l, r, id;
}; vector<node> A[maxn];

ll ans[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    stack<int> S; S.push(0); a[0] = a[n + 1] = n + 1; 
    for (int i = 1; i <= n + 1; ++i) {
        while (!S.empty() && a[i] > a[S.top()]) r[S.top()] = i, S.pop();
        l[i] = S.top(); S.push(i); 
    }
    for (int i = 1; i <= m; ++i) cin >> Q[i].first;
    for (int i = 1; i <= m; ++i) cin >> Q[i].second;
    for (int i = 1; i <= m; ++i) {
        A[Q[i].first - 1].push_back({ -1, Q[i].first, Q[i].second, i });
        A[Q[i].second].push_back({ 1, Q[i].first, Q[i].second, i });
    }
    for (int i = 1; i <= n; ++i) {
        Bit.update(l[i] + 1, r[i] - 1, 1);
        for (auto t : A[i]) ans[t.id] += t.type * Bit.query(t.l, t.r); 
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << " \n"[i == m];
    return 0; 
}