/** * Author: trviet * Studies at: Le Hong Phong High School for the Gifted **/ #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() constexpr int maxn = 1e6 + 6; int n, q, result[maxn]; struct FenwickTree { int sz; vector<int> bit; FenwickTree(int sz) { this->sz = sz; bit.resize(sz + 1); } void update(int i, int v) { for (; i <= sz; i += i & -i) bit[i] += v; } int get(int i) { int res = 0; for (; i > 0; i -= i & -i) res += bit[i]; return res; } }; struct Event { int x, y, z, id; bool operator < (Event o) const { return (x == o.x ? id < o.id : x > o.x); } } qr[maxn]; void ReadData() { cin.tie(0)->sync_with_stdio(0); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> qr[i].x >> qr[i].y; qr[i].z = qr[i].x + qr[i].y; } for (int i = n + 1; i <= n + q; ++i) { cin >> qr[i].x >> qr[i].y >> qr[i].z; qr[i].id = i; } } void Divide(int l, int r) { if (l == r) return; int m = (l + r) >> 1; Divide(l, m), Divide(m + 1, r); vector<Event> L, R; for (int i = l; i <= m; ++i) if (qr[i].id == 0) L.push_back(qr[i]); for (int i = m + 1; i <= r; ++i) if (qr[i].id != 0) R.push_back(qr[i]); sort(all(L), [&](Event a, Event b) { return a.y > b.y; }); sort(all(R), [&](Event a, Event b) { return a.y > b.y; }); FenwickTree ft(n + q); int j = 0; for (int i = 0; i < R.size(); ++i) { while (j < L.size() && L[j].y >= R[i].y) ft.update(L[j++].z, 1); result[R[i].id] += ft.get(n + q) - ft.get(R[i].z - 1); } } void Solve() { vector<int> values; for (int i = 1; i <= n + q; ++i) values.push_back(qr[i].z); sort(all(values)); values.resize(unique(all(values)) - values.begin()); for (int i = 1; i <= n + q; ++i) qr[i].z = lower_bound(all(values), qr[i].z) - values.begin() + 1; sort(qr + 1, qr + 1 + n + q); Divide(1, n + q); for (int i = n + 1; i <= n + q; ++i) cout << result[i] << "\n"; } int main() { ReadData(); Solve(); return 0; }