2018-2019 ICPC, NEERC, Northern Eurasia Finals K King Kog's Reception

問題

https://codeforces.com/contest/1089/problem/K

問題概要

以下のクエリを Q(<=3e5) 個処理する

• join t d : 時刻 t に開始して時間 d かかるタスクが予約される (joinでのt は全て異なる)
• cancel i : i 番目のクエリで追加されたタスクを削除
• query t : 現在予約されているタスクのうち時刻 t 以前(tも含む)に開始するタスクが全て終了する時刻 - t を求めよ

ただし, タスクは同時に1つしか行えない.

解法

追加と削除のクエリがあるので, 時系列をセグ木っぽく管理して追加クエリだけにする手法が脳裏をよぎる.
が, かなり大変な上に log が２個付くので TL 2s に収めるのはかなり厳しい.

実は, このタスクは時系列上のモノイドに落とすことができる.
具体的には, 区間に暇な時間がいくらあるかと, 区間終了時に終わっていないタスクがいくらあるか のペア.
なので, ただのセグメントツリーに載せるだけで解ける.

ソースコード

https://codeforces.com/contest/1089/submission/46514491

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

namespace segment_tree
{
    using T = pair<ll, ll>;
    const T id(-1, -1);
    T op(T a, T b) {
        if (a == id) return b;
        if (b == id) return a;
        ll pa, ea; tie(pa, ea) = a;
        ll pb, eb; tie(pb, eb) = b;
        if (ea == 0) ++pa;
        else --ea;
        return pb <= ea ? make_pair(pa, ea - pb + eb) : make_pair(pa + pb - ea, eb);
    }

    const int MAX = 1 << 20;
    T seg[MAX * 2];

    void init_seg() {
        for (int i = MAX; i < MAX * 2; ++i)
            seg[i] = make_pair(0, 0);
        for (int i = MAX - 1; i > 0; --i)
            seg[i] = op(seg[i << 1], seg[(i << 1) | 1]);
    }
    void update(int p, T val) {
        seg[p += MAX] = val;
        while (p >>= 1) seg[p] = op(seg[p << 1], seg[(p << 1) | 1]);
    }
    T find(int l, int r) {
        T res1 = id, res2 = id;
        for (l += MAX, r += MAX; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res1 = op(res1, seg[l++]);
            if (r & 1) res2 = op(seg[--r], res2);
        }
        return op(res1, res2);
    }
}

using namespace segment_tree;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int q;
    cin >> q;
    vector<int> t(q);
    init_seg();
    for (int i = 0; i < q; i++) {
        char c;
        cin >> c >> t[i]; --t[i];
        if (c == '+') {
            int d;
            cin >> d;
            update(t[i], make_pair(0, d));
        }
        else if (c == '-') {
            update(t[t[i]], make_pair(0, 0));
        }
        else {
            printf("%lld\n", find(0, t[i] + 1).second);
        }
    }
    return 0;
}