NC25214. Matrix
描述
M is MINIEYE's engineer and he is working on image segmentation. An image can be abstracted into a matrix of n × m, each element in the matrix is a positive integer; All rows in the matrix are numbered top-down from 1 to n, all columns from left to right are numbered from 1 to m.
The target of image segmentation is to view the 4-connected equal matrix elements as a whole and then segment the image into several parts, each part is 4-connected in the original matrix and consists of equal elements. The minimum number of segments in the segmentation is called image connectivity. When running the algorithm, ROI(Region of Interest) will be determined according to actual situation, which means image segmentation is not always based on the whole image, sometimes a pair of integers l, r will be given, and the segmentation will be done on a submatrix which consists of column l to column r.
M would like you to help him work out an algorithm which can calculate the connectivity of multiple ROI.
输入描述
The first row of input data includes 3 integers separated by spaces, n, m, q(1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105). n is the row of the matrix; m is the column of the matrix and q is the inquiry number.
For the following n rows, each row has m integers separated by spaces which represents image matrix. Matrix elements are positive integers smaller than 106.
For the following q rows, each row has two integers l and r separated by space(1 ≤ l ≤ r ≤ m), which represents each inquiry.
输出描述
For each inquiry, output one row that includes an integer to represent the connectivity of the corresponding submatrix.
示例1
输入:
4 5 4 1 1 1 1 1 1 2 2 3 3 1 1 1 2 5 4 4 5 5 5 1 5 2 5 1 2 4 5
输出:
6 7 3 4
C++11(clang++ 3.9) 解法, 执行用时: 848ms, 内存消耗: 26328K, 提交时间: 2019-04-23 23:55:37
#include<iostream>
using namespace std;
int n,m,q,s,map[11][100001],bitset[41];
struct{
int l;
int r;
int block;
int lc;
int rc;
int bitset[21];
}st[200001];
int find(int x){
if(bitset[x]==x)return x;
return (bitset[x]=find(bitset[x]));
}
int merge(int l[],int r[],int p,int mh[]){
int s=0;
for(int i=1;i<=2*n;i++)bitset[i]=l[i],bitset[i+2*n]=r[i]+2*n;
for(int i=1;i<=n;i++)
if(map[i][p]==map[i][p+1])
if(find(2*n+i)!=find(n+i)){
s++;
bitset[bitset[2*n+i]]=bitset[n+i];
}
for(int i=1;i<=n;i++){
mh[i]=find(i);
if(find(3*n+i)<=n)mh[n+i]=bitset[3*n+i];
else if(find(3*n+i)>3*n)mh[n+i]=bitset[3*n+i]-2*n;
else{
bitset[bitset[3*n+i]]=3*n+i;
bitset[3*n+i]=3*n+i;
mh[n+i]=n+i;
}
}
return s;
}
void build(int p){
if(st[p].l==st[p].r){
for(int i=1;i<=n;i++)st[p].bitset[i]=st[p].bitset[i+n]=i;
st[p].block=n;
for(int i=2;i<=n;i++)
if(map[i][st[p].l]==map[i-1][st[p].l]){
st[p].bitset[i]=st[p].bitset[i+n]=st[p].bitset[i-1];
st[p].block--;
}
return;
}
st[++s].l=st[p].l;
st[s].r=(st[p].l+st[p].r)>>1;
st[p].lc=s;
st[++s].l=((st[p].l+st[p].r)>>1)+1;
st[s].r=st[p].r;
st[p].rc=s;
build(st[p].lc);
build(st[p].rc);
st[p].block=st[st[p].lc].block+st[st[p].rc].block-merge(st[st[p].lc].bitset,st[st[p].rc].bitset,st[st[p].lc].r,st[p].bitset);
}
int work(int p,int l,int r,int bitset[]){
if(l==st[p].l&&r==st[p].r){
for(int i=1;i<=2*n;i++)bitset[i]=st[p].bitset[i];
return st[p].block;
}
if(r<=st[st[p].lc].r){
int temp[21];
int ans=work(st[p].lc,l,r,temp);
for(int i=1;i<=2*n;i++)bitset[i]=temp[i];
return ans;
}
if(l>=st[st[p].rc].l){
int temp[21];
int ans=work(st[p].rc,l,r,temp);
for(int i=1;i<=2*n;i++)bitset[i]=temp[i];
return ans;
}
int temp1[21],temp2[21];
int ans=work(st[p].lc,l,st[st[p].lc].r,temp1)+work(st[p].rc,st[st[p].rc].l,r,temp2);
int t=merge(temp1,temp2,st[st[p].lc].r,bitset);
ans-=t;
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>map[i][j];
st[s=1].l=1;st[1].r=m;
build(1);
while(q--){
int l,r;
cin>>l>>r;
int temp[21];
cout<<work(1,l,r,temp)<<endl;
}
return 0;
}