ABC407F - Sums of Sliding Window Maximum

問題

整数列$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] << "
";
}