Hamako Online Judge ukuku09 contest B ghoststudents

問題概要

https://hoj.hamako-ths.ed.jp/onlinejudge/problems/767
うくさんはICPC部に所属しています。
ある日いつものように部活に参加していたうくさんは、部活に来ている部員の数が最初より減っていることに気づきました。
そこで、出席記録から、ある日以降（その日を含む）に一体何人が部活に参加しているのかを調べることにしました。 ただし、うくさんは適当な性格をしているので、調べている途中で新しい記録が見つかることもあります。
ICPC部員にはそれぞれ1からNまでの独立な番号がつけられています。 ここで、ある日以降に部活に参加している人数を「その日以降に一度でも部活に参加した人」の数の和と定義します。
クエリ1:日目に()に番目()の生徒が部活に参加したことを表します。
クエリ2:日目を含むその日以降に()に出席した人数を求めたいことを表します。
クエリ2が入力として与えられた場合、それに対する出力をジャッジが受け取るまで以降の入力が行われないことに注意してください。
,

解説

動的BIT or seg木で解くことができる。
BITの int data[] を map<int,int>data みたいにすればちょっと重くなるけど
メモリを使う部分しか消費しないのでうれしい。
何人参加していないかという情報をノードに持たせて、ある人が参加していることが分かった時刻にいもす法っぽく端の情報を修正すればいい。(内部で対数時間で足し合わせるので)
C日目以降の出席人数が知りたいので、出席日が更新されるごとに、０日目の情報からその日の情報に情報を修正していき、
[0,C)の範囲にいるC日目以降に出席していない人数を求めればよい。

コード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

ll N, Q;
ll ans = 0LL;

struct BIT { // 0-index
        ll N;
        map<ll, int> data;
        BIT(ll n) {
                N = n;
        }
        void add(ll i, int w) { // a[i] += w
                i++;
                for (ll x = i; x <= N; x += x & -x) {
                        data[x] += w;
                }
        }
        int sum(ll i) {
                int ret = 0;
                i++;
                for (ll x = i; x > 0; x -= x & -x) {
                        ret += data[x];
                }
                return ret;
        }
};

ll last[100005];

int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);

        cin >> N >> Q;
        BIT bit(INT_MAX);
        bit.add(0, N);
        for(int i = 0; i < Q ; i++){
                int num; cin >> num;
                if (num == 1) {
                        int a, b; cin >> a >> b;
                        b--;
                        if (last[b] < a) {
                                bit.add(last[b], -1);
                                last[b] = a;
                                bit.add(last[b], 1);
                        }
                }
                else if (num == 2) {
                        int c; cin >> c;
                        ans = N - bit.sum(c - 1);
                        cout << ans << endl << flush;

                }
        }

        return 0;
}