JOI春合宿 2008-day4 typhoon

問題文 : 台風(pdf注意, 2ページ目~3ページ目)

解法 :
昔解いた気もするのですが, そのときはセグメント木を使っていました.

基本的には昔と方針はいっしょなのですが, 今回はReactive型の問題として出題されたときに対応できるよう, オンライン風に書いてみました. BIT と imos法を組み合わせた感じです.
1000番目, 2000番目, ..., i * 1000番目までの台風のデータを累積和としてもち, 1000個以内のデータを参照して各クエリをBITを用いて処理します. 1クエリあたり1000*lognくらいです.

最悪で1000 * 100000 * logn = 10^8 * lognくらいになりますが, 毎回1000回も参照しないですし, 2sec以内に答えを返すことが十分可能です. (printfのほうが遅くてつらいですが.)

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int bit[101][200002];
int scan[200002];
int n, m, k;
int s[100001], t[100001];
map<int, int> conv;


void add(int *p, int pos, int val)
{
	while (pos <= 2 * n + 2){
		p[pos] += val;
		pos += pos & -pos;
	}
}

int sum(int *p, int pos)
{
	int ret = 0;
	while (pos){
		ret += p[pos];
		pos &= (pos - 1);
	}
	return (ret);
}

int query(int no, int pos)
{
	if (no == 0) return (0);
	memset(scan, 0, sizeof(scan));
	
	for (int i = (no / 1000) * 1000 + 1; i <= no; i++){
		add(scan, conv[s[i]], 1);
		add(scan, conv[t[i] + 1], -1);
	}
	
	return (sum(scan, pos) + sum(bit[no / 1000], pos));
}


int main()
{
	int xs[200002];
	scanf("%d %d %d", &n, &m, &k);
	
	xs[0] = 1;
	xs[1] = n;
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &s[i], &t[i]);
		xs[i * 2 + 1] = s[i];
		xs[i * 2 + 2] = t[i] + 1;
	}
	
	sort(xs, xs + 2 * n + 2 + 1);
	
	int idx = 1;
	conv[xs[0]] = idx++;
	
	for (int i = 1; i <= 2 * n + 2; i++){
		if (xs[i] != xs[i - 1]) conv[xs[i]] = idx++;
	}
	
	for (int i = 1; i <= n; i++){
		add(scan, conv[s[i]], 1);
		add(scan, conv[t[i] + 1], -1);
		if (i % 1000 == 0){
			memcpy(bit[i / 1000], scan, sizeof(scan));
		}
	}
	
	for (int i = 0; i < m; i++){
		int p, q, r;
		scanf("%d %d %d", &p, &q, &r);
		p = conv[*(upper_bound(xs, xs + 2 * n + 2 + 1, p) - 1)];
		printf("%d\n", query(r, p) - query(q - 1, p));
	}
	
	return (0);
}