TopCoder SRM 580 Div1 Medium ShoutterDiv1

問題

うさぎがn匹いて、それぞれs[i]からt[i]の間部屋にいた。
部屋にいた時間の区間が長さ0以上の共通部分をもつうさぎは友達になった。

うさぎが全員twitter的なサービスで自己紹介を、他の全てのうさぎに見せたい。
友達の自己紹介は直接見られるが、友達の友達（や、さらにその友達）に自己紹介を見せるためには、友達にRT的なことをしてもらう必要がある。
最低何回RTが必要になるか、求めよ。

制約条件

0≦s[i], t[i]≦9999
n≦2500

方針

dp[l][r] := s[l]からt[r]の区間部屋にいたうさぎが全員自己紹介を見られるとき、
それを全てのうさぎに見せるまでに必要なRTの数
というDPをした。

まず、union-findを使って区間が共通部分をもつうさぎをマージする。
全部のうさぎがマージできなかったら-1

次に、DPをするが、愚直にやるとO(n^3)なので工夫する必要がある。
i番目の人の自己紹介を全員に広めるとき、
rec(i, i)を左右に伸ばしていきたい。

s[i], t[i]を覆う区間をもつうさぎがいなかったら、区間の交わるうさぎのうち、貪欲に一番遠くまで区間を延ばせるものを選べばよい。

区間をすっぽり覆ううさぎがいるとき、区間を覆ううさぎを使う回数は高々1回でよい。
（極大なうさぎを使えばよいから。）
ということは、最初の1回を区間を覆ううさぎのどれかで全通り試せばよいということがわかる。
残りは貪欲にやればよい。

区間の交わるうさぎのうち、もっとも伸ばせるうさぎを求めるのは、適当にRMQを使えばよい。

const int SZ = 2500, MX = 10010;
int n, s[SZ], t[SZ], dp[SZ][SZ], p[SZ];

int root(int x){
	return x == p[x] ? x : p[x] = root(p[x]);
}

int R[MX], L[MX];
int sum(int *bit, int i){
	int res = -inf;
	for(; i; i -= i & -i) res = max(res, bit[i]);
	return res;
}
void add(int *bit, int i, int x){
	for(; i < MX; i += i & -i) bit[i] = max(bit[i], x);
}

int mnt, mxs, tos[MX], tot[MX];
int rec(int l, int r){
	int &res = dp[l][r];
	if(res >= 0) return res;
	if(s[l] <= mnt && t[r] >= mxs) return res = 0;
	res = inf;
	int nl = tos[-sum(L, 10005 - s[l])], nr = tot[sum(R, t[r])];
	if(s[nl] < s[l]) res = min(res, rec(nl, r) + 1);
	if(t[nr] > t[r]) res = min(res, rec(l, nr) + 1);
	return res;
}

class ShoutterDiv1 {
	public:
	int count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1) {
		n = 0;
		rep(i, s1.size()) rep(j, s1[i].size()){
			s[n] = 1000 * (s1000[i][j] - '0') + 100 * (s100[i][j] - '0') +
				10 * (s10[i][j]- '0') + s1[i][j] - '0' + 1;
			t[n] = 1000 * (t1000[i][j] - '0') + 100 * (t100[i][j] - '0') +
				10 * (t10[i][j] - '0') + t1[i][j] - '0' + 1;
			n++;
		}
		rep(i, n) p[i] = i;
		rep(i, n) rep(j, n) if(t[i] >= s[j] && s[i] <= t[j]){
			int a = root(i), b = root(j);
			if(a != b) p[a] = b;
		}
		rep(i, n) if(root(i) != root(0)) return -1;
		
		memset(dp, -1, sizeof(dp));
		rep(i, MX) L[i] = R[i] = -inf;
		
		mnt = inf, mxs = 0;
		rep(i, n){
			add(R, s[i], t[i]);
			add(L, 10005 - t[i], -s[i]);
			mnt = min(mnt, t[i]);
			mxs = max(mxs, s[i]);
			tos[s[i]] = i;
			tot[t[i]] = i;
		}
		
		int ans = 0;
		rep(i, n){
			int tmp = rec(i, i);
			rep(j, n) if(s[j] <= s[i] && t[i] <= t[j]) tmp = min(tmp, 1 + rec(j, j));
			ans += tmp;
		}
		return ans;
	}
}