P6406 [COCI2014-2015#2] Norma

· · 题解

\texttt{Preface}

学数据结构学坏脑子，只会无脑线段树了。

\texttt{Description}

P6406 [COCI2014-2015#2] Norma

\texttt{Solution}

设 \max(l, r) = \max\{a_l, a_{l+1},\cdots, a_r\},\min(l,r)=\min\{a_l,a_{l+1},\cdots,a_r\}。

看到这种对于所有区间求一个式子的和，我们可以套路地转换成枚举 r，求出：

\sum_{l = 1}^r \max(l,r)\times \min(l,r) \times(r-l+1)

我们可以用两个单调栈，这样求 \max(l,r) 和 \min(l,r) 就变成了区间加或者区间覆盖了。

然后考虑 (r-l+1)，我们可以把它拆成 r+1 和 -l，这样我们只需要分别维护：

\sum_{i = 1}^r \max(i, r)\times \min(i,l) \sum_{i = 1}^r \max(i, r)\times \min(i,l) \times i

用线段树维护即可，后面那个式子下传懒标记时需要用到等差数列求和公式。

\texttt{Code} 
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9;
int n, a[500005], ans = 0;
struct node {
    int l, r, sa1, sb1, sa2, sb2, ans1, ans2;
} tr[2000005];
struct tag {
    int a1, a2;
} lazy[2000005];
#define ls (p * 2)
#define rs (p * 2 + 1)
void pushup(int p) {
    tr[p].sa1 = (tr[ls].sa1 + tr[rs].sa1) % mod;
    tr[p].sb1 = (tr[ls].sb1 + tr[rs].sb1) % mod;
    tr[p].sa2 = (tr[ls].sa2 + tr[rs].sa2) % mod;
    tr[p].sb2 = (tr[ls].sb2 + tr[rs].sb2) % mod;
    tr[p].ans1 = (tr[ls].ans1 + tr[rs].ans1) % mod;
    tr[p].ans2 = (tr[ls].ans2 + tr[rs].ans2) % mod; 
}
void build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;
    tr[p].sa1 = tr[p].sb1 = tr[p].sa2 = tr[p].sb2 = 0;
    tr[p].ans1 = tr[p].ans2 = 0;
    if (l == r) return ;
    int mid = (l + r) / 2;
    build(ls, l, mid), build(rs, mid + 1, r);
}
void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
void add_tag(int p, tag t) {
    if (t.a1) {
        add(lazy[p].a1, t.a1);
        add(tr[p].ans1, 1ll * tr[p].sb1 * t.a1 % mod);
        add(tr[p].ans2, 1ll * tr[p].sb2 * t.a1 % mod);
        add(tr[p].sa1, 1ll * (tr[p].r - tr[p].l + 1) * t.a1 % mod);
        add(tr[p].sa2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a1 % mod);
    }
    if (t.a2) {
        add(lazy[p].a2, t.a2);
        add(tr[p].ans1, 1ll * tr[p].sa1 * t.a2 % mod);
        add(tr[p].ans2, 1ll * tr[p].sa2 * t.a2 % mod);
        add(tr[p].sb1, 1ll * (tr[p].r - tr[p].l + 1) * t.a2 % mod);
        add(tr[p].sb2, 1ll * (tr[p].l + tr[p].r) * (tr[p].r - tr[p].l + 1) / 2 % mod * t.a2 % mod);
    }
}
void pushdown(int p) {
    if (lazy[p].a1 or lazy[p].a2) {
        add_tag(ls, lazy[p]);
        add_tag(rs, lazy[p]);
        lazy[p] = (tag){0, 0};
    }
}
void update(int p, int x, int y, tag t) {
    if (tr[p].l >= x && tr[p].r <= y) {
        return add_tag(p, t), void();
    }
    pushdown(p);
    int mid = (tr[p].l + tr[p].r) / 2;
    if (x <= mid) update(ls, x, y, t);
    if (mid < y) update(rs, x, y, t);
    pushup(p);
}
#undef ls
#undef rs
int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);
    stack <int> sta1, sta2;
    sta1.push(0), sta2.push(0);
    for (int i = 1; i <= n; ++i) {
        while (sta1.top() && a[ sta1.top() ] <= a[i]) {
            int x = sta1.top(), val = a[ sta1.top() ]; sta1.pop();
            update(1, sta1.top() + 1, x, (tag){a[i] - val, 0});
        }
        sta1.push(i), update(1, i, i, (tag){a[i], 0});
        while (sta2.top() && a[ sta2.top() ] >= a[i]) {
            int x = sta2.top(), val = a[ sta2.top() ]; sta2.pop();
            update(1, sta2.top() + 1, x, (tag){0, a[i] - val + mod});
        }
        sta2.push(i), update(1, i, i, (tag){0, a[i]});
        (ans += (1ll * tr[1].ans1 * (i + 1) % mod - tr[1].ans2 + mod) % mod) %= mod;
    }
    cout << ans << '\n';
    return 0;
}
\texttt{Thanks for watching!}