Codeforces #269 Div2 E. MUH and Lots and Lots of Segments

Div2の割に難易度が高い問題。
http://codeforces.com/contest/471/problem/E

問題

2次元座標上で、格子点を端点とし、X軸またはY軸に平行な線分がN個与えられる。
このうち、以下の条件を満たすように筆を動かし、線分のうち一部領域を塗る。

• 筆は任意の線分上の任意の格子点で降ろし、筆を上げることができる。筆を降ろしてあげるまでの1セット分だけ線分を塗ることができる。
• 筆は線分上を動くことで線分を塗ることができる。線分上を動く場合は、1度に距離1ずつ移動する。
• 同じ場所を複数回移動しても良い。
• 塗った線分が閉路を作ってはならない。

1度に塗れる線分の領域の最大総長を求めよ。

解法

筆はすでに塗った場所を再度移動できるので、連結した線分群は基本的に全部塗ることができる。
ただし閉路ができるといけないので、閉路1個につき1か所塗らない場所を作れば閉路が1個減る。
すなわち、（連結した線分の総長－閉路数）が求める長さである。

次に閉路判定だが、X軸に平行なY軸に平行な線分が交わる場合Union-Findでそれらを連結していき、すでにUnion-Findで連結している線分同士がさらに交わる場合、閉路が1個できる。

ここまでで、連結した線分と閉路の両方の数え上げが可能だが、交点判定にO(N^2)かかるので交点を愚直に列挙すると間に合わない。
よって以下のように高速化する。

• まずY座標を座標圧縮する。
• X座標左方向から順にline sweepしていき、今のX座標に何個横棒があるかset及びBITで管理していく。
  • 縦棒を処理する場合は、BITを使って縦棒が何本の横棒と交差するかO(logN)で判定できる。
  • そのうち何個がUnion-Findで異なるか判定する必要がある。よって、横棒を1本ずつ管理するのではなく、同じグループの横棒をまとめて管理する。各グループでY座標の下端と上端を保持する。この下端・上端の対を以下セグメントと表現する。

各X座標について以下のように処理していく。

• そのX座標を左端とする横棒を追加する。
  • その棒のY座標を上端かつ下端とするセグメントを追加する。
  • すでにあるセグメントの真ん中に横棒を追加する場合、既存のセグメントを分割する必要がある。
• そのX座標上にある縦棒を処理する。
  • その縦棒の範囲内にある横棒の数をBITでカウントしつつ、交差するセグメント群をUnionしていく。
• そのX座標を右端とする横棒を削除する。
  • この横棒がセグメントの上端または下端の場合、セグメントの上端・下端の位置が変化する。

かなりめんどくさいが、全体でO(N*logN)で処理できる。

class UF {
	public:
	static const int ufmax=200052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> bt;

int N;
int X1[300000],Y1[300000],X2[300000],Y2[300000];
ll L[300000];
set<int> E, SY;
map<int,vector<pair<int,int> > > H1,V,H2;
UF uf;
set<pair<pair<int,int>,int> > S; // bottom,top,id
map<int,int> Ys;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	Ys[1<<30]=Ys[-1<<30]=0;
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		if(X1[i]>X2[i]) swap(X1[i],X2[i]);
		if(Y1[i]>Y2[i]) swap(Y1[i],Y2[i]);
		L[i]=((ll)X2[i])-X1[i]+Y2[i]-Y1[i];
		Ys[Y1[i]]=Ys[Y2[i]]=0;
	}
	
	i=0;
	ITR(it,Ys) it->second=i++;
	
	FOR(i,N) {
		Y1[i]=Ys[Y1[i]];
		Y2[i]=Ys[Y2[i]];
		E.insert(X1[i]);
		E.insert(X2[i]);
		if(X1[i]==X2[i]) V[X1[i]].push_back(make_pair(Y1[i],i));
		if(X1[i]!=X2[i]) H1[X1[i]].push_back(make_pair(Y1[i],i)),H2[X2[i]].push_back(make_pair(Y1[i],i));
	}
	
	ITR(it,E) {
		set<pair<pair<int,int>,int> >::iterator seg,seg2;
		set<int>::iterator sit,sit2;
		pair<pair<int,int>,int> p,p2;
		
		ITR(it2,H1[*it]) { // add
			seg=S.lower_bound(make_pair(make_pair(it2->first,0),0));
			if(seg!=S.end() && seg->first.second<=it2->first) { //insert
				p=make_pair(make_pair(0,seg->first.second),seg->second);
				p2=make_pair(make_pair(seg->first.first,0),seg->second);
				S.erase(seg);
				
				sit=SY.lower_bound(it2->first);
				p2.first.second=*sit;
				sit--;
				p.first.first=*sit;
				S.insert(p);
				S.insert(p2);
			}
			
			p=make_pair(make_pair(it2->first,it2->first),it2->second);
			bt.update(it2->first,1);
			SY.insert(it2->first);
			S.insert(p);
		}
		
		ITR(it2,V[*it]) { // conn
			seg=S.lower_bound(make_pair(make_pair(Y1[it2->second],0),0));
			seg2=S.lower_bound(make_pair(make_pair(Y2[it2->second],0),0));
			if(seg2!=S.end() && seg2->first.second<=Y2[it2->second]) seg2++;
			if(seg==seg2) continue;
			
			if(seg->first.first>Y2[it2->second] && seg->first.second<Y1[it2->second]) {
				// in single seg
				if(bt.total(Y2[it2->second])-bt.total(Y1[it2->second]-1)==0) continue;
			}
			
			pair<pair<int,int>,int> p=make_pair(make_pair(-1<<30,1<<30),it2->second);
			L[it2->second] -= bt.total(Y2[it2->second])-bt.total(Y1[it2->second]-1);
			
			// conn seg-seg2
			for(; seg!=seg2;) {
				x=uf[p.second]; y=uf[seg->second];
				if(x!=y) L[x]=L[y]=L[x]+L[y]+1, uf.unite(x,y);
				p.first.first=max(p.first.first,seg->first.first);
				p.first.second=min(p.first.second,seg->first.second);
				S.erase(seg++);
			}
			S.insert(p);
		}
		
		ITR(it2,H2[*it]) { // del
			seg=S.lower_bound(make_pair(make_pair(it2->first,0),0));
			p=*seg;
			S.erase(seg);
			bt.update(it2->first,-1);
			SY.erase(it2->first);
			if(p.first.first==p.first.second) continue;
			if(p.first.first==it2->first) {
				sit=SY.lower_bound(it2->first);
				p.first.first=*(--sit);
			}
			else if(p.first.second==it2->first) {
				p.first.second=*SY.lower_bound(it2->first);
			}
			S.insert(p);
			
		}
	}
	
	ll ma=0;
	FOR(i,N) ma=max(ma,L[i]);
	
	cout << ma << endl;
}

まとめ

Div1Eでもこんな正答者の少ない問題は少ないのでは…。