题解：P10764 [BalticOI 2024] Wall

· · 题解

考虑分别求 \sum H_i 和 \sum h_i，而显然 \sum h_i = \sum 2^{n - 1}(a_i + b_i)，仅需考虑 \sum H_i。

我们注意到 H_i = \sum_{x = 1}^{V} [x \leq H_i]，于是我们考虑从 1 到 V 枚举 x，检查是否 x \leq H_i。而我们知道 H_i = \min\{\max_{j = 1}^{i}\{h_j\}, \max_{j = i}^{n}\{h_j\}\}，于是 H_i \geq i 当且仅当 (\exist j \in [1, i])(h_j \geq x) 且 (\exist j \in [j, n])(h_j \geq x)。

如果存在 j \leq i 和 j \geq i 都满足 a_j \geq x, b_j \geq x，那么显然任意选都能满足 H_i \geq x，于是贡献即为 2^n。记最小的满足 a_j \geq x, b_j \geq x 的 j 为 L，最大的为 R，那么 i \in [L, R] 都有 2^n 的贡献。我们考量 i \in [1, L)，此时右侧仍然无需在意，但是左侧必须有一个 h_j \geq x。我们记 v_i = [a_i \geq x \vee b_i \geq x], s_i = \sum_{j = 1}^{i} v_i，那么贡献即为任意选的方案数减去 i 左侧选不出任何一个 1 的方案数，即 2^n - 2^{n - s_i}。对称地，i \in (R, n] 的贡献即为 2^n - 2^{n - s_n - s_{i - 1}}。

如果不存在满足上文条件的 j，那么 i 左侧要选出一个 1，右侧要选出一个 1，方案数即为

\begin{aligned} (2^{s_{i - 1}} - 1)(2^{s_n - s_i} - 1)2^{n - s_n} + v_i2^{n - 1} &= 2^{n - v_i} - 2^{n - s_i} - 2^{n - (s_n - s_{i - 1})} + 2^{n - s_n} + v_i2^{n - 1}\\ &= 2^{n} - 2^{n - s_i} - 2^{n - (s_n - s_{i - 1})} + 2^{n - s_n}\\ \end{aligned}

观察形式，综上，我们得出结论：

  1. 无论何时，i 总有贡献 2^n。
  2. 如果不存在 j \leq i 使得 a_j \geq x, b_j \geq x，那么额外贡献 -2^{n - s_i}。
  3. 如果不存在 j \geq i 满足该条件，额外贡献 -2^{n - (s_n - s_{i - 1})}。
  4. 特别地，如果 2 和 3 同时满足，额外贡献 2^{n - s_n}。

直接使用线段树维护 s_i 和上述一些值即可做到 \mathcal{O}(n\log n)，但是实现并不优美。

我们考虑对于线段树上一个节点 [l, r] 维护 val, pre, suf，分别表示仅考虑 [l, r] 的子串时上文中第 4 条的值、第 2、3 条 [l, r] 的值之和。考虑记 w_i = 2 - v_i，那么显然 val_{[l, r]} = \prod_{i = l}^{r} w_i = val_{ls} \times val_{rs}。我们又注意到满足贡献条件时 2^{n - s_i} = (2^{n - i} \times w_i) \times 2^{(i - 1) - s_{i - 1}}，而 2^{(i - 1) - s_{i - 1}} 在 val 中维护，可以在 pushup 中将左儿子的贡献乘到右儿子上合并，于是我们可以对叶节点记 pre = 2^{n - i} \times w_i，非叶节点有 pre = pre_{ls} + pre_{rs} \times val_{ls}。类似地也有 suf = suf_{rs} + suf_{ls} \times val_{rs}。

这样我们只需要修改 w_i 即可，仅需维护一棵单点修改、全局查询的线段树，时间复杂度 \mathcal{O}(n\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 5e5 + 10, mod = 1e9 + 7;

int n, res = 0;
int a[maxn], b[maxn], pwr[maxn], val[maxn];
vector<int> tmp, ad[maxn << 1];

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

namespace segtree{
    struct{
        int l, r, pre, suf, val;
    } tree[maxn << 2];
    inline void pushup(int index){
        tree[index].pre = mod_add(tree[index << 1].pre, (long long)tree[index << 1 | 1].pre * tree[index << 1].val % mod);
        tree[index].suf = mod_add(tree[index << 1 | 1].suf, (long long)tree[index << 1].suf * tree[index << 1 | 1].val % mod);
        tree[index].val = (long long)tree[index << 1].val * tree[index << 1 | 1].val % mod;
    }
    inline void build(int index, int l, int r){
        tree[index].l = l, tree[index].r = r;
        if (l == r){
            return;
        }
        const int mid = l + r >> 1;
        build(index << 1, l, mid), build(index << 1 | 1, mid + 1, r);
    }
    inline void modify(int index, int x, int k){
        if (tree[index].l == tree[index].r){
            return tree[index].pre = (long long)pwr[n - x] * k % mod, tree[index].suf = (long long)pwr[x - 1] * k % mod, tree[index].val = k, void();
        }
        const int mid = tree[index].l + tree[index].r >> 1;
        modify(index << 1 | x > mid, x, k), pushup(index);
    }
}

using namespace segtree;

inline int pos(int x){
    return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin() + 1;
}

int main(){
    scanf("%d", &n), build(1, 1, n), pwr[0] = 1;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]), tmp.push_back(a[i]), pwr[i] = (pwr[i - 1] << 1) % mod;
    }
    for (int i = 1; i <= n; i++){
        scanf("%d", &b[i]), tmp.push_back(b[i]);
        self_mod_add(res, mod - (long long)pwr[n - 1] * mod_add(a[i], b[i]) % mod);
    }
    sort(tmp.begin(), tmp.end()), tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()), self_mod_add(res, (long long)tmp[0] * n % mod * pwr[n] % mod);
    for (int i = 1; i <= n; i++){
        ad[pos(a[i])].push_back(i), ad[pos(b[i])].push_back(i);
    }
    for (int i = 2; i <= tmp.size(); i++){
        for (auto x: ad[i - 1]){
            modify(1, x, ++val[x]);
        }
        self_mod_add(res, (long long)(tmp[i - 1] - tmp[i - 2]) * mod_add((long long)n * pwr[n] % mod, mod - tree[1].pre, mod - tree[1].suf, (long long)n * tree[1].val % mod) % mod);
    }
    printf("%d", res);

return 0;
}