これは本番解けてもよかったな。
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位でもいいと思うんだけどね。