专栏文章

题解：P10764 [BalticOI 2024] Wall

CClaire0918
P10764题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minr95uv
此快照首次捕获于
2025/12/02 07:03
3 个月前
此快照最后确认于
2025/12/02 07:03
3 个月前
查看原文
考虑分别求 ∑Hi\sum H_i 和 ∑hi\sum h_i，而显然 ∑hi=∑2n−1(ai+bi)\sum h_i = \sum 2^{n - 1}(a_i + b_i)，仅需考虑 ∑Hi\sum H_i。
我们注意到 Hi=∑x=1V[x≤Hi]H_i = \sum_{x = 1}^{V} [x \leq H_i]，于是我们考虑从 11 到 VV 枚举 xx，检查是否 x≤Hix \leq H_i。而我们知道 Hi=min⁡{max⁡j=1i{hj},max⁡j=in{hj}}H_i = \min\{\max_{j = 1}^{i}\{h_j\}, \max_{j = i}^{n}\{h_j\}\}，于是 Hi≥iH_i \geq i 当且仅当 (∃j∈[1,i])(hj≥x)(\exist j \in [1, i])(h_j \geq x) 且 (∃j∈[j,n])(hj≥x)(\exist j \in [j, n])(h_j \geq x)。
如果存在 j≤ij \leq i 和 j≥ij \geq i 都满足 aj≥x,bj≥xa_j \geq x, b_j \geq x，那么显然任意选都能满足 Hi≥xH_i \geq x，于是贡献即为 2n2^n。记最小的满足 aj≥x,bj≥xa_j \geq x, b_j \geq x 的 jj 为 LL，最大的为 RR，那么 i∈[L,R]i \in [L, R] 都有 2n2^n 的贡献。我们考量 i∈[1,L)i \in [1, L)，此时右侧仍然无需在意，但是左侧必须有一个 hj≥xh_j \geq x。我们记 vi=[ai≥x∨bi≥x],si=∑j=1iviv_i = [a_i \geq x \vee b_i \geq x], s_i = \sum_{j = 1}^{i} v_i，那么贡献即为任意选的方案数减去 ii 左侧选不出任何一个 11 的方案数，即 2n−2n−si2^n - 2^{n - s_i}。对称地，i∈(R,n]i \in (R, n] 的贡献即为 2n−2n−sn−si−12^n - 2^{n - s_n - s_{i - 1}}。
如果不存在满足上文条件的 jj，那么 ii 左侧要选出一个 11，右侧要选出一个 11，方案数即为
(2si−1−1)(2sn−si−1)2n−sn+vi2n−1=2n−vi−2n−si−2n−(sn−si−1)+2n−sn+vi2n−1=2n−2n−si−2n−(sn−si−1)+2n−sn\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. 无论何时，ii 总有贡献 2n2^n。
  2. 如果不存在 j≤ij \leq i 使得 aj≥x,bj≥xa_j \geq x, b_j \geq x，那么额外贡献 −2n−si-2^{n - s_i}。
  3. 如果不存在 j≥ij \geq i 满足该条件，额外贡献 −2n−(sn−si−1)-2^{n - (s_n - s_{i - 1})}。
  4. 特别地，如果 2 和 3 同时满足，额外贡献 2n−sn2^{n - s_n}。
直接使用线段树维护 sis_i 和上述一些值即可做到 O(nlog⁡n)\mathcal{O}(n\log n)，但是实现并不优美。
我们考虑对于线段树上一个节点 [l,r][l, r] 维护 val,pre,sufval, pre, suf，分别表示仅考虑 [l,r][l, r] 的子串时上文中第 4 条的值、第 2、3 条 [l,r][l, r] 的值之和。考虑记 wi=2−viw_i = 2 - v_i，那么显然 val[l,r]=∏i=lrwi=valls×valrsval_{[l, r]} = \prod_{i = l}^{r} w_i = val_{ls} \times val_{rs}。我们又注意到满足贡献条件时 2n−si=(2n−i×wi)×2(i−1)−si−12^{n - s_i} = (2^{n - i} \times w_i) \times 2^{(i - 1) - s_{i - 1}}，而 2(i−1)−si−12^{(i - 1) - s_{i - 1}} 在 valval 中维护，可以在 pushup 中将左儿子的贡献乘到右儿子上合并，于是我们可以对叶节点记 pre=2n−i×wipre = 2^{n - i} \times w_i，非叶节点有 pre=prels+prers×vallspre = pre_{ls} + pre_{rs} \times val_{ls}。类似地也有 suf=sufrs+sufls×valrssuf = suf_{rs} + suf_{ls} \times val_{rs}。
这样我们只需要修改 wiw_i 即可，仅需维护一棵单点修改、全局查询的线段树，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...