ABC407F - Sums of Sliding Window Maximum

#imos法

問題

整数列 \(A\) が与えられます。 \(k=1, 2, \cdots, N\) について、以下の問題を解いて下さい。
- \(A\) の長さ \(k\) の連続部分列は \(N-k+1\) 個存在するが、それぞれについての最大値を合計したものを求めよ。

解法

問題をそのまま解くのは不可能なので、代わりに各値について寄与を考える。すなわち、 \(A_i\) が長さ \(k\) の連続部分列の最大値として現れるのは何回か？を考えれば良い。
\(A_i\) が長さ \(k\) の連続部分列の最大値として現れることを考えるために、 \(A_i\) 以下の要素が、 \(A_i\) の左右にいくつ伸びているか？を知りたい。これは std::set と lower_bound を用いることで問題なく取得することができる。以降、 \(l\) を \(1\leq l \leq i\) かつ \(\max_{j=l}^i A_j = A_i\) を満たす最小値、 \(r\) を \(i+r \leq N\) かつ \(\max_{j=i}^{i+r} A_{i+j} = A_{i+r}\) を満たす最大値として定義する。
この区間において、 \(i\) を含んでかつ長さ \(k\) の連続部分列がいくつ存在するかを考えよう 。
まず、 \(k \leq \text{min}(l, r)\) である間は、ちょうど \(k\) 個の連続部分列が存在する。これは左右にいくらでも伸ばせるので、 \(i\) を長さ \(k\) のうち何番目に置くか？という話を考えれば良い。次に \(\min(l,r) < k \leq \max(l,r)\) である間、片端が \(\min(l,r)\) より伸ばせず、もう片方はいくらでも伸ばせるので \(\min(l,r)\) のままである。最後に \(\max(l,r) < k\) の場合は、両端に自由度がなくなっていくので、 \(\min(l,r)-(k-\max(l,r))\) となる。
答え \(C_k(k=1,2,\cdots,N)\) に対する寄与の回数を、例えば \(l=4,r=2\) で考えると、 \(C_1 = 1, C_2 = 2, C_3 = 2, C_4 = 2, C_5 = 1, C_6 = 0, \cdots\) となる。これは左右が等差数列、真ん中が同じ値になっていて簡単に区間演算をするのが難しい が、「増加部分の+と減少部分の-を区間加算」ができればimos法で求めることができるので、区間加算の遅延セグメントツリーを用いれば良い 。
以上を実装することで、全体で \(O(N\log N)\) 時間で解くことができる。 提出(C++, 249ms)

// 区間加算にしか興味がないので、Sの演算は何でもOK
using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

void solve() {
    int n; cin>> n;
    auto a = i64_vec_IN(n);
    vll indicate(n,0); iota(all(indicate), 0);
    sort(all(indicate), [&](const ll& i, const ll& j) {
        if(a[i] == a[j]) return i>j;
        else return a[i]<a[j];
    });
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(n+1);
    rep(i,n) seg.set(i,0);

    set<ll> notChecked;
    rep(i,n) notChecked.insert(i);
    notChecked.insert(-1);
    notChecked.insert(n);

    for(auto i: indicate) {
        notChecked.erase(i);
        auto itr = notChecked.upper_bound(i);
        ll right = *itr;
        itr--;
        ll left = *itr;
        ll r_d = right - i;
        ll l_d = i - left;

        ll itrval = r_d + l_d - 1;
        seg.apply(0, min(l_d, r_d), a[i]);
        seg.apply(max(l_d, r_d), itrval+1, -a[i]);
    }

    ll cur = 0;
    vll ans(n);
    rep(i,n) {
        cur += seg.get(i);
        ans[i] = cur;
    }
    rep(i,n) cout << ans[i] << "\n";
}