abc106d ac segtree/2d prefixsum

// Problem: D - AtCoder Express 2
// Contest: AtCoder - AtCoder Beginner Contest 106
// URL: https://atcoder.jp/contests/abc106/tasks/abc106_d
// Memory Limit: 976 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&...values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;
using atcoder::segtree;

using S = int;
S op(S a, S b) { return a + b; }
S e() { return 0; }

int n, m, q;
vector<pii> lr;
vector<pii> pq;

int main(int argc, char **argv)
{
    cin >> n >> m >> q;
    lr = vector<pii>(m);
    for (int i = 0; i < m; ++i)
        cin >> lr[i].first >> lr[i].second;
    pq = vector<pii>(q);
    for (int i = 0; i < q; ++i)
        cin >> pq[i].first >> pq[i].second;
    using piii = pair<pii, int>;
    auto pqi = vector<piii>(q);
    for (int i = 0; i < q; ++i)
        pqi[i] = {pq[i], i};
    sort(pqi.begin(), pqi.end());
    sort(lr.begin(), lr.end());
    vector<S> v(501);
    for (auto [l, r] : lr)
        v[r] += 1;
    segtree<S, op, e> seg(v);
    int i1 = 0, i2 = 0;
    vector<int> ans(q);
    for (i2 = 0; i2 < q; ++i2) {
        while (i1 < m && lr[i1].first < pqi[i2].first.first) {
            seg.set(lr[i1].second, seg.get(lr[i1].second) - 1);
            i1++;
        }
        ans[pqi[i2].second] = seg.prod(pqi[i2].first.first, pqi[i2].first.second + 1);
    }
    for (int i = 0; i < q; ++i)
        cout << ans[i] << endl;
    return 0;
}

int main1(int argc, char **argv)
{
    cin >> n >> m >> q;
    lr = vector<pii>(m);
    for (int i = 0; i < m; ++i)
        cin >> lr[i].first >> lr[i].second;
    pq = vector<pii>(q);
    for (int i = 0; i < q; ++i)
        cin >> pq[i].first >> pq[i].second;

    auto arr = vv<int>(502);
    for (auto [l, r] : lr)
        arr[l][r] += 1;

    auto dp = vv<int>(502);
    for (int l = 500; l >= 0; --l)
        for (int r = l; r <= 500; ++r)
            dp[l][r] = dp[l][r - 1] + dp[l + 1][r] - dp[l + 1][r - 1] + arr[l][r];

    for (auto [l, r] : pq)
        cout << dp[l][r] << endl;

    return 0;
};