Codeforces 369(#216 Div2 only) E. Valera and Queries

問題

x軸上にn本の線分がある。i番目の線分は[l[i], r[i]]である。
これらの線分に対して以下のm個のクエリに答えよ。


i番目のクエリではk[i]個の点が与えられる。それぞれの座標はx[i][j].
これらの点を一つ以上含む線分の本数を出力する。

制約条件

n, m≦3*10^5
1≦l[i]≦r[i]≦10^6
入力される点の総数は3*10^5を超えない。

方針

点を一つも含まない線分の本数を数えて、nから引けばいい。
点を一つも含まない線分は、点と点の厳密に内側にある線分の本数を数えればよい。


これは、rごとに線分と区間をソートするとはやくできて、
rの小さい順に線分と区間をソート、
線分が出てきたらlに+1する。
区間が出てきたら、lより大rより小に含まれる+1の個数を数えればいい。


区間に含まれる+1の個数はbinary indexed treeを使えばはやく求まる。

ソースコード

const int N = 300010;
const int MX = 1000100;
int n, m, l[N], r[N], ans[N];

int bit[MX];

inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}

int main(){
	
	scanf("%d%d", &n, &m);
	
	vector<pair<pi, int> > q;
	
	rep(i, n){
		scanf("%d%d", l + i, r + i);
		q.pb(mp(mp(r[i], l[i]), -1));
	}
	
	rep(i, m){
		int cnt;
		vi v;
		v.pb(0);
		
		scanf("%d", &cnt);
		rep(j, cnt){
			int p;
			scanf("%d", &p);
			v.pb(p);
		}
		v.pb(1000001);
		
		rep(j, v.size() - 1){
			q.pb(mp(mp(v[j + 1], v[j]), i));
		}
	}
	
	sort(all(q));
	
	rep(i, q.size()){
		
		int a = q[i].first.second + 1, b = q[i].first.first + 1;
		int id = q[i].second;
		
		if(id < 0) add(a, 1);
		else ans[id] += sum(b - 1) - sum(a);
	}
	
	rep(i, m) cout << n - ans[i] << endl;
	
	return 0;
}

range treeを使ってx座標が[l, r]にあるy座標がt以下の点の個数を答える的なやり方でやったらO(nlog^2n)とかの計算量のはずだけどTLEだった。

const int N = 300010;
int n, m, l[N], r[N], sz;

vi xs;
vi data[1048576];

inline void init(int k, int a, int b){
	
	if(a + 1 == b){
		sort(all(data[k]));
		return;
	}
	const int l = k * 2 + 1, r = k * 2 + 2;
	
	init(l, a, (a + b) / 2);
	init(r, (a + b) / 2, b);
	
	data[k].resize(data[l].size() + data[r].size());
	
	merge(all(data[l]), all(data[r]), data[k].begin());
}
inline int query(int y, int l, int r, int k, int a, int b){
	
	if(r <= a || l >= b) return 0;
	if(l <= a && b <= r){
		return lower_bound(all(data[k]), y) - data[k].begin();
	}
	const int m = (a + b) / 2;
	const int lch = query(y, l, r, k * 2 + 1, a, m);
	const int rch = query(y, l, r, k * 2 + 2, m, b);
	
	return lch + rch;
}

int main(){
	
	scanf("%d%d", &n, &m);
	
	rep(i, n){
		scanf("%d%d", l + i, r + i);
		xs.pb(l[i]);
	}
	xs.pb(0); xs.pb(inf);
	sort(all(xs));
	xs.erase(unique(all(xs)), xs.end());
	
	for(sz = 1; sz < xs.size(); sz *= 2);
	
	rep(i, n){
		l[i] = lower_bound(all(xs), l[i]) - xs.begin();
		data[l[i] + sz - 1].pb(r[i]);
	}
	
	init(0, 0, sz);
	
	while(m--){
		
		int cnt;
		vi v;
		
		v.pb(0); v.pb(inf);
		
		scanf("%d", &cnt);
		
		rep(i, cnt){
			int p;
			scanf("%d", &p);
			v.pb(p);
		}
		sort(all(v));
		v.erase(unique(all(v)), v.end());
		
		int ans = n;
		
		rep(i, v.size() - 1){
			
			int a = upper_bound(all(xs), v[i]) - xs.begin();
			int b = lower_bound(all(xs), v[i + 1]) - xs.begin();
			
			//cerr<<"a: "<<a<<" b: "<<b<<endl;
			
			ans -= query(v[i + 1], a, b, 0, 0, sz);
		}
		cout << ans << endl;
	}
	
	return 0;
}