読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

JOI2008春合宿Day4 台風(Typhoon)

座標圧縮 セグメント木/BIT

最近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;
}