---
tags: JOI
---
# JOI2021 春合宿 Day1-3 フードコート (Food Court)

## 問題文

https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/foodcourt.pdf
https://atcoder.jp/contests/joisc2021/tasks/joisc2021_c

## 考察

クエリを順に走査して加入や脱退を管理しようとすると、何人目がどの団体かを管理するのが大変そうです。(何人並んでいるかを別に求めた後永続セグ木 + 二分探索で log 2 つかな)
そこで、店舗を順に走査しましょう。加入イベント・脱退イベントの挿入・削除をして、ある時刻での先頭から $B$ 番目がどの団体かを求められればいいです。
こういう retroactive なやつの実現方法といえば、セグ木です。どの団体か求めるのはなかなか難しいですが、何人並んでいるかくらいはわかるでしょう。

(脱退イベントの人数, 加入イベントの人数) は $(a_1, b_1) + (a_2, b_2) = (a_1 + \max(a_2 - b_1, 0), b_2 + \max(b_1 - a_2, 0))$ でマージでき、単位元は $(0, 0)$ なので、これをセグ木に乗せれば何人並んでいるかがわかります。

これで後ろから何番目かがわかるので、あとは加入イベントのみのセグ木で二分探索を行えば、どのタイミングでの加入かがわかります。

## 実装

$O(N + Q \log Q)$

https://atcoder.jp/contests/joisc2021/submissions/29604941

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

struct Event{
    // 以前に並んでいた人のうち leave 人までが去って、新たに join 人が加わる
    ll leave = 0, join = 0;
    Event operator+(const Event& a) const {
        if(join <= a.leave) return {leave + a.leave - join, a.join};
        else return {leave, join + a.join - a.leave};
    }
};
template<class T> struct SegmentTree{
    vector<T> data;
    ll size = 1;
    SegmentTree(ll n){
        while(n > size) size <<= 1;
        data.resize(size * 2);
    }
    void set(ll i, T a){
        i += size;
        data[i] = a;
        while(i >>= 1) data[i] = data[i << 1] + data[i << 1 | 1];
    }
    // fold [0, r)
    T get(ll r) const {
        T ans{};
        ll l = size;
        r += size;
        while(l != r){
            if(r & 1) ans = data[--r] + ans;
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
    // min l s.t. f(get(l, r)) == true
    template<class F> ll min_left(ll r, F f) const {
        ll l = size;
        r += size;
        T a{};
        while(1){
            if(l == r) return 0;
            if(r & 1){
                T b = data[r - 1] + a;
                if(f(b)){
                    a = b;
                    r--;
                }
                else break;
            }
            l >>= 1;
            r >>= 1;
        }
        while(l < size){
            l <<= 1;
            r <<= 1;
            T b = data[r - 1] + a;
            if(f(b)){
                a = b;
                r--;
            }
        }
        return r - size;
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll N, M, Q;
    cin >> N >> M >> Q;
    // {フードコート, クエリ時刻, leave, join}
    vector<array<ll, 4>> events;
    // {フードコート, クエリ時刻, 前から B 人目, 何番目の出力}
    vector<array<ll, 4>> query;
    vector<ll> ans;
    // クエリ時刻 -> 団体番号
    vector<ll> group(Q);
    for(ll t = 0; t < Q; t++){
        ll type;
        cin >> type;
        if(type == 1){
            ll L, R, C, K;
            cin >> L >> R >> C >> K;
            L--;
            group[t] = C;
            events.push_back({L, t, 0, K});
            events.push_back({R, t, 0, 0});
        }
        else if(type == 2){
            ll L, R, K;
            cin >> L >> R >> K;
            L--;
            events.push_back({L, t, K, 0});
            events.push_back({R, t, 0, 0});
        }
        else{
            ll A, B;
            cin >> A >> B;
            A--;
            query.push_back({A, t, B, (ll)ans.size()});
            ans.emplace_back();
        }
    }
    sort(events.begin(), events.end(), greater<>{});
    sort(query.begin(), query.end(), greater<>{});
    SegmentTree<Event> seg(Q);
    // join の総和を数える。前から B 人目を見つけるのに使う。
    SegmentTree<ll> seg2(Q);
    for(ll f = 0; f < N; f++){
        while(events.size() && events.back()[0] == f){
            auto [f, t, leave, join] = events.back();
            events.pop_back();
            seg.set(t, {leave, join});
            seg2.set(t, join);
        }
        while(query.size() && query.back()[0] == f){
            auto [f, t, B, i] = query.back();
            query.pop_back();
            // 後ろから B 人目 (0-indexed)
            B = seg.get(t).join - B;
            if(B < 0) continue;
            // 時刻 t から遡って B 人を超える瞬間が答えの団体
            const ll t2 = seg2.min_left(t, [&, B = B](ll b){ return b <= B; }) - 1;
            ans[i] = group[t2];
        }
    }
    for(ll x : ans) cout << x << '\n';
}