AtCoder Beginner Contest 106 D - AtCoder Express 2

atcoder.jp

区間を二次元座標とみなし、二次元累積和で。

一方、クエリ先読みして区間を終端ソートすると、終端が前の区間から順に確認していくことで問題を解くことができる。終端の順番を固定し、始端の分布をBITでもち、和をで得ることができ、計算量はとなる。

• 二次元累積和 ver

template<typename T>
class TwoDimCumsum {
public:
    int H,W;
    vector<vector<T>> d;
    TwoDimCumsum(T _H, T _W):H(_H),W(_W),d(_H+1,vector<T>(_W+1,0)){}
    // 1-indexed
    void add(int x, int y, int a){
        d[x][y] += a;
    }
    void build(){
        for(int i = 1; i <= H; ++i){
            for(int j = 1; j <= W; ++j){
                d[i][j] += d[i-1][j];
                d[i][j] += d[i][j-1];
                d[i][j] -= d[i-1][j-1];
            }
        }
    }
    //[sx, gx] & [sy, gy]
    //1-indexed
    T query(int sx, int sy, int gx, int gy){
        return d[gx][gy] - d[sx-1][gy] - d[gx][sy-1] + d[sx-1][sy-1];
    }
    //confirm the 2d vector
    void debug(){
        for(int i = 0;i <= H;++i){
            for(int j = 0; j <= W; ++j){
                cerr<<d[i][j]<<((j == W) ? "\n":" ");
            }
        }
    }
};

int main() {

    int N, M, Q;
    cin >> N >> M >> Q;
    TwoDimCumsum<ll> Cum(N, N);
    rep(i,M){
        int l, r;
        cin >> l >> r;
        Cum.add(l,r,1);
    }
    Cum.build();
    while(Q --> 0){
        int p, q;
        cin >> p >> q;
        //[p, N] && [0, q]
        cout << Cum.query(p,0,N,q) << endl;
    }
}

• 終端ソート ver

template<typename T>
class BIT{
  public:
    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){
        vector<T> tmp(N);
    }
    // k-th number (k is 1 - indexed)
    T get(int k){
        T res = 0;
        int sz = 1;
        while(sz < (int)data.size()) sz <<= 1;
        for(int i = sz / 2; i > 0; i >>= 1){
            if(res + i <= N && data[res + i] < k){
                k -= data[res + i];
                res += i;
            }
        }
        return res + 1;
    }
};
struct Section{
    int l;
    int r;
    int type;
    int idx;
    Section(int l_, int r_, int type_, int idx_):l(l_), r(r_), type(type_), idx(idx_){};
    bool operator<(const Section& b){
        return make_pair(r, idx) < make_pair(b.r, b.idx);
    }
};
int main() {

    int N, M, Q;
    cin >> N >> M >> Q;
    vector<Section> Sections;
    rep(i,M){
        int l, r;
        cin >> l >> r;
        Section x(l, r, 0, -1);
        Sections.push_back(x);
    }
    rep(i,Q){
        int l, r;
        cin >> l >> r;
        Section y(l, r, 1, i);
        Sections.push_back(y);
    }
    sort(all(Sections));
    BIT<ll> B(1000);
    vector<int> ans(Q);
    rep(i,M+Q){
        if(Sections[i].type){
            ans[Sections[i].idx] =  B.sum(Sections[i].l, Sections[i].r);
        }
        else{
            B.add(Sections[i].l, 1);
        }
    }
    rep(i,Q){
        cout << ans[i] << endl;
    }
}