kmjp's blog

競技プログラミング参加記です

Codeforces #416 Div2 E. Vladik and Entertaining Flags

これは本番解けてもよかったな。
http://codeforces.com/contest/811/problem/E

問題

N*Mのグリッドが与えられる。
各マスには数字が設定されている。
同じ数字同士の隣接マスは連結しているとみなす。

Q個のクエリ[L[i],R[i]]が与えられる。このグリッドのL[i]列~R[i]列内のマス目の連結成分の数を求めよ。

解法

区間に対するSegTreeで頑張る。
区間に対し両端の数字と、区間内の色の総和を求めておき、連結していこう。
連結の際はUnion-Findの要領で色数を計算していく。

TLがかなり厳しいので注意。
入力データ量も多いので、cinよりscanfの方が安全。

const int FD=40;
int finddata[FD];
int find(int x) {
	if(finddata[x]==-1) return x;
	return finddata[x]=find(finddata[x]);
}


int N,M,Q;
int C[10][101010];
int NC;

const int NV=1<<17;
vector<int> val[NV*2];

vector<int> merge(vector<int> A, vector<int> B) {
	if(B.empty()) return A;
	if(A.empty()) return B;
	int NA=A[2*N+1],y;
	
	vector<int> R(2*N+4);
	R[2*N]=A[2*N]+B[2*N];
	R[2*N+2]=A[2*N+2];
	R[2*N+3]=B[2*N+3];
	
	MINUS(finddata);
	FOR(y,N) if(C[y][A[2*N+3]]==C[y][B[2*N+2]]) {
		int a=find(A[N+y]);
		int b=find(NA+B[y]);
		if(a!=b) {
			R[2*N]--;
			finddata[a]=b;
		}
	}
	
	int m[40]={},u=0;
	
	FOR(y,N) {
		if(m[find(A[y])]==0) m[find(A[y])]=++u;
		R[y]=m[find(A[y])]-1;
	}
	FOR(y,N) {
		if(m[find(NA+B[N+y])]==0) m[find(NA+B[N+y])]=++u;
		R[N+y]=m[find(NA+B[N+y])]-1;
	}
	R[2*N+1]=u;
	return R;
}

vector<int> getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
	if(r<=x || y<=l) return {};
	if(x<=l && r<=y) return val[k];
	return merge(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	//cin>>N>>M>>Q;
	scanf("%d%d%d",&N,&M,&Q);
	FOR(y,N) FOR(x,M) scanf("%d",&C[y][x]);
	FOR(i,NV*2) val[i].resize(2*N+4);
	FOR(x,M) {
		for(y=1;y<N;y++) {
			if(C[y][x]==C[y-1][x]) val[NV+x][y]=val[NV+x][N+y]=val[NV+x][y-1];
			else val[NV+x][y]=val[NV+x][N+y]=val[NV+x][y-1]+1;
		}
		val[NV+x][2*N]=val[NV+x][2*N+1]=val[NV+x][N-1]+1;
		val[NV+x][2*N+2]=val[NV+x][2*N+3]=x;
	}
	for(i=NV-1;i>=1;i--) val[i]=merge(val[i*2],val[i*2+1]);
	FOR(i,Q) {
		scanf("%d%d",&x,&y);
		auto v=getval(x-1,y);
		_P("%d\n",v[2*N]);
	}
}

まとめ

N=5位でもいいと思うんだけどね。

広告を非表示にする