ARC045 B - ドキドキデート大作戦高橋君

B - ドキドキデート大作戦高橋君

概要

隣接した教室がN個あり、1からNと付番されている。
M個の掃除割り当てがあり、i番目の割り当てではsi番目からti番目の教室を掃除することになっている。
i番目の割り当ては、iの割り当てのすべての教室がi以外の割り当てでも掃除されるとき、さぼれることとする。
さぼれる割り当ての個数と、さぼれる割り当ての番号を出力せよ。

制約

1 ≦ N ≦ 300000
1 ≦ M ≦ 100000

方針

①各教室について、その教室がいくつの割り当てで掃除されるかを計算する。
②各割り当てについて、その割り当てのすべての教室の①の割り当て数が2以上なら、
その割り当てはさぼれる。

①はいもす法で計算するとO(N + M)。
②はセグメント木を使うとO(M * log(N))

感想

セグメント木を初めて使いました。
const int max_n = 1 << 26;の設定は注意が必要そう。

②の計算は、模範解答だとセグメント木を使わずに、割り当て数が2未満の教室に1を立てて、区間を累積和で計算していました。

解答

Submission #4755726 - AtCoder Regular Contest 045

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
const int INF = 1 << 28;
const int max_n = 1 << 26;
 
int seg_N;
int dat[2*max_n-1];
 
void init(int n_){
	// 簡単のため、要素数は2べきにする
	seg_N = 1;
	while(seg_N < n_) seg_N *= 2;
 
	rep(i,2*seg_N-1) dat[i] = INF;
}
 
// k番目の値をaに変更
void update(int k, int a){
	k += seg_N-1;
	dat[k] = a;
 
	while(k > 0){
		k = (k-1)/2;
		dat[k] = min(dat[k*2+1], dat[k*2+2]);
	}
}
 
// [a,b) の最小値を呼び出す
// 外からはquery(a, b, 0, 0, N) と呼び出す
ll query(int a, int b, int k, int l, int r){
	if(r <= a || b <= l) return INF;
		if(a <= l && r <= b) return dat[k];
		else{
			ll vl = query(a, b, k * 2 + 1, l, (l+r)/2);
			ll vr = query(a, b, k * 2 + 2, (l+r)/2, r);
			return min(vl,vr);
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M;
	cin >> N >> M;
 
	init(N);
 
	vector<int> v(N+1, 0);
	vector<int> s(M, 0);
	vector<int> t(M, 0);
 
	rep(i, M){
		cin >> s[i] >> t[i];
		s[i]--;
		t[i]--;
 
		v[s[i]]++;
		v[t[i]+1]--;
	}
 
	rep(i, N){
		v[i+1] += v[i];
		update(i, v[i]);
	}
 
	int cnt = 0;
	vector<int> ans;
	rep(i, M){
		if(query(s[i], t[i]+1, 0, 0, seg_N) >= 2){
			cnt++;
			ans.push_back(i+1);
		}
	}
 
	cout << cnt << endl;
	rep(i, cnt){
		cout << ans[i] << endl;
	}
 
}