JOI2008春合宿Day4 台風(Typhoon)
最近Ubuntuと格闘しています。
解法
クエリを、x座標(家の位置)でソートするというだけの座圧をします。
あとはそれを順番に見ていきますが、クエリに応えるために、台風の番号を区間としたBITを持ちます。
今の座標に範囲が被さっている台風だけを持っていたいので、台風の範囲に入る/台風の範囲から抜ける ときにBITをいじります。
実装
実は初めてBITを実装しました。
BITが1-indexedなので区間操作で戸惑いました。
using namespace std; #define int long long const int MAX = 1e5; struct Query { int id, p, l, r; bool operator < (const Query &q) const { return p < q.p; } }; struct Event { int p, id; Event() {} Event(int _p, int _id) { p = _p; id = _id; } bool operator < (const Event &e) const { return p > e.p; } }; int N, M, K, A[MAX], B[MAX]; Query query[MAX]; int bit[MAX + 1]; int GetSum(int i) { int res = 0; while (i > 0) { res += bit[i]; i -= i&-i; } return res; } void Add(int i, int v) { i++; while (i <= N) { bit[i] += v; i += i&-i; } } void Forward(priority_queue<Event> &pq, int x, int v) { while (!pq.empty() && pq.top().p <= x) { Add(pq.top().id, v); pq.pop(); } } signed main() { priority_queue<Event> pv, mv; cin >> N >> M >> K; for (int i = 0; i < N; i++) { scanf("%lld%lld", A + i, B + i); A[i]--; pv.push(Event(A[i], i)); mv.push(Event(B[i], i)); } for (int i = 0; i < M; i++) { query[i].id = i; scanf("%lld%lld%lld", &query[i].p, &query[i].l, &query[i].r); query[i].p--; query[i].l--; } sort(query, query + M); int ans[MAX]; for (int i = 0; i < M; i++) { Forward(pv, query[i].p, +1); Forward(mv, query[i].p, -1); ans[query[i].id] = GetSum(query[i].r) - GetSum(query[i].l); } for (int i = 0; i < M; i++) { printf("%lld\n", ans[i]); } return 0; }