ABC106 AtCoder Express 2

問題

D - AtCoder Express 2

解く前に考えていたこと

区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。
実装の際に盛大にバグらせたので戒めとして書きました。

解法

+ クエリ先読みのオフラインアルゴリズムというらしい

#include<bits/stdc++.h>
using ll  = long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? 1e9:1e18)
using namespace std;
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using pii = pair<int,int>;
using piii = pair<int,pii>;

int bit [1000] = {},n;
int sum(int i){
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add (int i,int x){
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}
signed main(){
    int m,q; cin >> n >> m >> q;
    vector<piii>v( m + q);
    rep(i,m+q) {
        int a,b; cin >> a >> b;
        piii temp;
        temp.first = a, temp.second.first = b;
        temp.second.second = i;
        v[i] = temp;
    }
    sort (all(v),[](auto const x,auto const y) {
        return (
                x.second.first < y.second.first  or
                (x.second.first == y.second.first and x.second.second < y.second.second)
                );
    });
    int ans[100000] = {};
    erep(e,v){
        int left = e.first;
        int right = e.second.first;
        bool isQuery = e.second.second >= m;
        int index = e.second.second - m;
        if (isQuery){
            ans[index] =  sum(right) - sum (left - 1);
        } else {
            add(left, 1);
        }
    }
    rep(i,q) cout << ans[i] << endl;
}

9/6　追記
一応segtreeの解答も載せておこうかな
https://beta.atcoder.jp/contests/abc106/submissions/3096327