MMA Contest 015 L Slime Structure

挨拶

初めまして。hikkiと申します。

MMA Contest 015のTesterをやっておりました。

まずは解いて下さった方に感謝申し上げます。大盛況とのことでとても嬉しく思います。

続いてWriterのNafmo2さん、Sepa38さん、dyktr_06さんにも感謝いたします。ありがとうございます。

最後に他のTesterの方々にも感謝いたします。特にphocomさんには電通大競プロサークルを再び動かしてくれたこともあり、貴重な経験をさせていただき頭が上がりません。

また次回、コンテストを行う機会がありましたら是非ともよろしくお願いいたします。もしかしたらその時はWriterやるかもしれないのでその時はよろしくお願いいたします。

問題

ProblemId = 9596 - yukicoder

方針自体は見えやすいような気がします。そこからどう解を出すかがポイント。

解説

前提として必要な知識は、最大部分配列を高速に求める方法です。

それに関する参考文献があるようで意外となかったのですが、蟻本の「分割統治法」の箇所や、以下の部分を知っておくとよいでしょう。

Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog

今回は点変更も行うため、これをセグメントツリー上にて行いたいです。

これに関する記事もあり、以下となります。

最大部分配列問題(連続部分列の総和の最大値)をセグ木に載せる - hotmanの備忘録とライブラリ置き場

分割統治法のよい練習となるため、最大部分列問題を知らない方は一度お考えください。

結合律と単位元(モノイドを構成する必要条件)を満たすようにするためにはどんな演算でセグメントツリーに載せれば良いか、何を保持しておく必要があるか、電車の帰りにも考えるとよい脳トレになるでしょう。

ともあれ、上を元にして一点変更と区間最大値を出すセグメントツリーを作ることでこの問題は解けそうです。

しかし、このままでは上手くいきません。何故でしょうか。

セグメントツリーのコンストラクタの計算量は要素数を$${N}$$ とした時、$${\Theta(N)}$$となります。

従って、今回Pureな設計を行うと、$${\Theta(\Sigma B)}$$かかり、意地の悪い入力を与えられた際、計算が間に合いません。

これをどのようにして解消するかが課題となります。

ここで、この問題をよく観察してみましょう。

例えば、サンプル$${1}$$ の初期状態(クエリが与えられる前)は、

となっております。

さて、ここで、

2 2 7

としたクエリが与えられた場合、最大部分配列の値はいくつになるでしょうか。

答えはもちろん、

であり、値は$${6}$$ です。

さてここで、最大部分配列となる箇所の「始点と終点」が知りたいぞ！というモチベーションがわいたとします。

この場合、例えば$${6}$$ 番目が終点となることはあるでしょうか。

答えはほとんどノーです。$${6}$$ 番目まで行くくらいならば$${5}$$ 番目で止めるし、仮に$${6}$$ 番目まで行くとするなら$${7}$$ 番目まで行かないと値が減ってしまいます。

これとほとんど同様の考え方を行うことで、値がマイナスとなる箇所を始点として部分配列を求める事もほとんど有り得ません。

例外として1点の和しか聞かれていない、あるいは周りを見渡してもそこかしろがマイナスである場合、しぶしぶマイナスとなる箇所を始点及び終点とします。

しかし、その他の場合はほとんどプラスとなる箇所を始点及び終点とするはずです。

2 2 2 // 1点のみ
2 6 7 // マイナスだらけ!

などです。

同様に、$${4}$$ 番目も終点となることは少なそうです。

なぜなら、$${5}$$ 番目が正の値であり、$${4}$$番目で止めるくらいなら$${5}$$番目まで伸ばすためです。

ただしこれはクエリ$${2}$$ が指し示す範囲が十分大きい場合である事に注意してください。

クエリ$${2}$$ で$${r=4}$$となっている場合、当然終点は$${5}$$ となることはあり得ません。  

数式としても見てみましょう。

$${S_{x, y}}$$を閉区間$${[x, y]}$$の部分和と定義します。

$${\displaystyle \max_{\substack{l \leq x \leq r \\ l \leq y \leq r}} S_{x, y} = S_{L, R}}$$

となる$${(L, R)}$$の候補となりうる箇所はどこかを考えます。

例えば$${S_{6, 6} < 0}$$であるため、

$${S_{4, 6}=S_{4, 5}+S_{6, 6} < S_{4, 5}}$$

となります。他の箇所も数式を立てご確認ください。区間の包含に近いかもしれないです。

これらをまとめると$${L, R}$$の候補となりうる箇所は、

• クエリ$${2}$$ で与えられた$${l}$$ と$${r}$$

• 値が切り替わる箇所(とその周り)

となります。これは高々$${2*(N+Q)}$$個しかないため、始点と終点となりえない箇所は1つのスライムとしてまとめる事で、コンストラクタにかかる計算量を削減できます。

イメージとしては以下の通りです。

これはクエリ先読みと座標圧縮と呼ばれるテクニックであり、前計算に$${O((N+Q) \log (N+Q))}$$を要することで、コンストラクタを$${\Theta (N+Q)}$$とするテクニックです。

これにより、セグメントツリー上の二分探索も$${O(\log (N+Q))}$$となり、結果として、合計$${O(Q \log (N+Q))}$$でクエリ$${2}$$を処理できます。

座標圧縮はクエリ$${1}$$ に対しても自然に組み込むことができ、クエリ$${1}$$ で変更される箇所を事前に分けておく($${1}$$ 点で別途管理する)ことで問題なく処理できます。

以上をコードにまとめて、この問題を解くことが出来ます。

ここまでお読みいただきありがとうございました。

そして、今日電気通信大学に来ていただいた方、そうでない方、解いていただきありがとうございました。

それではまたどこかで。

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<long long, long long>;
using vpll = vector<pll>;
using mint = modint1000000007;
const long double EPS = 1e-18;
const long long INF = 1e15;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}
// 最大部分配列をセグメントツリーに載せる。
struct S {
    ll left_max;
    ll right_max;
    ll kukan_max;
    ll sum;
};
S op(S a, S b) {
    return S{max(a.left_max, a.sum + b.left_max),
             max(b.right_max, b.sum + a.right_max),
             max(max(a.kukan_max, b.kukan_max), a.right_max + b.left_max),
             a.sum + b.sum};
}
S e() { return S{-INF, -INF, -INF, 0ll}; }
int main() {
    INIT;
    ll N;
    cin >> N;
    vll A(1e5 + 100), B(1e5 + 100);
    rrep(i, N) { cin >> A[i] >> B[i]; }
    ll Q;
    cin >> Q;
    vll q(1e5 + 100), a(1e5 + 100), b(1e5 + 100);
    vll num;
    num.push_back(0ll);
    // 累積和を計算。
    rrep(i, N) { num.push_back(num[i - 1] + B[i]); }
    vll numnum = num;
    // 値が変わる前後を記録しておく。
    rrep(i, N) {
        num.push_back(numnum[i] - 1);
        num.push_back(numnum[i] + 1);
    }
    // クエリ先読み。こちらも値の前後を入れておく。
    rrep(i, Q) {
        cin >> q[i] >> a[i] >> b[i];
        num.push_back(a[i] - 1);
        num.push_back(a[i]);
        num.push_back(a[i] + 1);
        if (q[i] == 2) {
            num.push_back(b[i] - 1);
            num.push_back(b[i]);
            num.push_back(b[i] + 1);
        }
    }
    // 座標圧縮。
    sort(ALL(num));
    num.erase(unique(ALL(num)), num.end());
    ll su = num.size();
    segtree<S, op, e> seg(su + 1);
    rrep(i, num.size() - 1) {
        // 二分探索により対応するAの値を探す。
        auto itr = lower_bound(ALL(numnum), num[i]);
        ll l = itr - numnum.begin();
        ll haba = num[i] - num[i - 1];
        seg.set(i, S{A[l] * haba, A[l] * haba, A[l] * haba, A[l] * haba});
    }
    rrep(i, Q) {
        if (q[i] == 1) {
            // 二分探索により、本来の値から圧縮後の値を探す。
            ll l = lower_bound(ALL(num), a[i]) - num.begin();
            seg.set(l, S{b[i], b[i], b[i], b[i]});
        } else {
            // 二分探索により、本来の値から圧縮後の値を探す。
            ll l = lower_bound(ALL(num), a[i]) - num.begin();
            ll r = lower_bound(ALL(num), b[i]) - num.begin();
            cout << seg.prod(l, r + 1).kukan_max << endl;
        }
    }
}