1 /*  2     线段树+并查集维护  3     线段树维护每列的信息   4     le 代表区间左端一列连通性的信息   5     ri 代表区间右端一列连通性的信息  6     w,b 分别代表白色连通块和黑色连通块的个数  7     lb 代表区间左端一列黑白点的信息   8     rb 代表区间右端一列黑白点的信息  9     tmp用来暂时存储连通块个数  10 */ 11 #include<cstdio> 12 #include<cstring> 13 #include<iostream> 14 #include<algorithm> 15 #define MAXN 210 16  17 using namespace std; 18  19 struct node { 20     int l,r; 21     int w,b; 22     int le[MAXN],ri[MAXN]; 23     int lb[MAXN],rb[MAXN]; 24 }; 25 node t[MAXN<<2]; 26  27 int a[MAXN][MAXN],n,m; 28  29 int fa[MAXN<<2],tmp[MAXN<<2]; 30  31 inline void read(int&x) {  32     int f=1;x=0;char c=getchar();  33     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}  34     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}  35     x=x*f;  36 }  37  38 inline int find(int x) { 39     if(x==fa[x]) return fa[x]; 40     else return fa[x]=find(fa[x]); 41 } 42  43 inline void up(int now) { 44     t[now].w=t[now<<1].w+t[now*2+1].w; 45     t[now].b=t[now<<1].b+t[now*2+1].b; 46     memcpy(t[now].lb,t[now<<1].lb,sizeof t[now].lb); 47     memcpy(t[now].rb,t[now*2+1].rb,sizeof t[now].rb); 48     for(int i=1;i<=3*n;i++) fa[i]=i; 49     for(int i=1;i<=n;i++)  50       t[now*2+1].le[i]+=2*n,t[now*2+1].ri[i]+=2*n; 51     for(int i=1;i<=n;i++) { 52         int x=t[now<<1].ri[i],y=t[now*2+1].le[i]; 53             if(find(x)!=find(y)&&t[now<<1].rb[i]==t[now*2+1].lb[i]) { 54             fa[find(x)]=find(y); 55             if(t[now<<1].rb[i]) t[now].b--; 56             else t[now].w--; 57         } 58     } 59     for(int i=1;i<=n;i++)  60       t[now].le[i]=find(t[now<<1].le[i]),t[now].ri[i]=find(t[now*2+1].ri[i]); 61     for(int i=1;i<=n;i++)  62       tmp[i<<1]=t[now].le[i],tmp[(i<<1)-1]=t[now].ri[i]; 63     sort(tmp+1,tmp+1+2*n); 64     int maxdata=http://www.mamicode.com/unique(tmp+1,tmp+1+2*n)-tmp-1; 65     for(int i=1;i<=n;i++) 66       t[now].le[i]=lower_bound(tmp+1,tmp+1+maxdata,t[now].le[i])-tmp,t[now].ri[i]=lower_bound(tmp+1,tmp+1+maxdata,t[now].ri[i])-tmp; 67     for(int i=1;i<=n;i++) t[now*2+1].le[i]-=2*n,t[now*2+1].ri[i]-=2*n; 68     return; 69 } 70  71 void build_tree(int now,int l,int r) { 72     t[now].l=l; 73     t[now].r=r; 74     if(l==r) { 75         int tot=0; 76         for(int i=1;i<=n;i++) { 77             if(a[i][l]!=a[i-1][l]) { 78                 tot++; 79                 if(a[i][l]) t[now].b++; 80                 else t[now].w++; 81             } 82             t[now].le[i]=t[now].ri[i]=tot; 83             t[now].lb[i]=t[now].rb[i]=a[i][l]; 84         } 85         return; 86     } 87     int mid=(l+r)>>1; 88     build_tree(now<<1,l,mid); 89     build_tree(now*2+1,mid+1,r); 90     up(now); 91 } 92  93 void modify(int now,int pos) { 94     if(t[now].l==t[now].r) { 95         int tot=0; 96         t[now].b=0; 97         t[now].w=0; 98         for(int i=1;i<=n;i++) { 99             if(a[i][pos]!=a[i-1][pos]) {100                 tot++;101                 if(a[i][pos]) t[now].b++;102                 else t[now].w++;103             }104             t[now].le[i]=t[now].ri[i]=tot;105             t[now].lb[i]=t[now].rb[i]=a[i][pos];106         }107         return;108     }109     int mid=(t[now].l+t[now].r)>>1;110     if(pos<=mid) modify(now<<1,pos);111     else modify(now*2+1,pos);112     up(now);113 }114 115 int main() {116     read(n);117     for(int i=1;i<=n;i++) {118         a[0][i]=-1;119         for(int j=1;j<=n;j++)120           read(a[i][j]);121     }122     build_tree(1,1,n);123     read(m);124     for(int i=1;i<=m;i++) {125         int x,y;126         read(x);read(y);127         a[x][y]^=1;128         modify(1,y);129         printf("%d %d\n",t[1].b,t[1].w);130     }131     return 0;132 }