8VC Venture Cup 2016 - Final Round B. Factory Repairs

問題

codeforces.com

解法

問題文の解釈をするのが一番難しいです。

問題文の意味を書きます。

指ぬき(?)を作る機械が 1 つある。修理する前は 1 日 b 個, 修理した後は 1 日に a 個の指ぬきを作れる。修理をするのには k 日かかり, 修理開始日が p だとすると, p, p+1, ..., p+k-1 日目には指ぬきを全く作れない。
で, クエリが与えられる。クエリの意味は以下の通り。

• 1 d a … 「ちょうど」d 日目に指ぬきを「1 つ」作って欲しいという依頼が, a 個追加で来る。
• 2 p … p 日目から機械の修理をした場合, 今までのクエリで来た以来の内最大でいくつの依頼を達成できるのかを求める。

1 d a の説明で「ちょうど」と強調しているのは, つまり d-1 日目より前に指ぬきを作り溜めしておいて d 日目に渡す, というのが NG であることを示します。これがよくわからなかった…

で, 問題の意味が分かれば簡単ですね。セグメント木を使います。

p 日目より前のものは, 最大で b 個の指ぬきを作れるという条件の下で区間の和を取ります。 p+k 日より後のものは, 最大で a 個の指ぬきを作れるという条件の下で区間の和を取ります。

// セグメント木
// update: k 番目の値に a 加える
// query: [l, r) の区間の和を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, 0);
    }
    inline T merge(T x, T y) {
        return x + y;
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] += a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k, a, b, q;
    cin >> n >> k >> a >> b >> q;
    ST<ll> sega(n+10), segb(n+10);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int di, ai;
            cin >> di >> ai;
            {
                ll tmp = sega.query(di, di+1);
                ll add = min<ll>(a, tmp+ai) - tmp;
                sega.update(di, add);
            }
            {
                ll tmp = segb.query(di, di+1);
                ll add = min<ll>(b, tmp+ai) - tmp;
                segb.update(di, add);
            }
        } else {
            int p;
            cin >> p;
            cout << segb.query(0, p) + sega.query(p+k, n+1) << endl;
        }
    }
    return 0;
}