codeforces 811E Vladik and Entertaining Flags

codeforces 811E Vladik and Entertaining Flags

​​ In his spare time Vladik estimates beauty of the flags. Every flag could be represented as the matrix n × m which consists of positive integers. Let’s define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:

But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied. Help Vladik to calculate the beauty for some segments of the given flag. Input First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — dimensions of flag matrix and number of segments respectively. Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106. Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know. Output For each segment print the result on the corresponding line. Example Input 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 Output 6 7 3 4 Note Partitioning on components for every segment from first test case:

这题在jy的提醒下想到线段树可是 该怎么维护连通性呢，确实想到了要利用并查集维护连通性，可是 看了题解才知道这个并查集似乎和我们平时用的不太一样，直接用点坐标做并查集实则是不行的

而且这题的一个关键就是我们需要记下来每个状态下我的并查集是什么状态 这个并查集记的是我染色的颜色之间的从属关系

建树的时候 l==r时 将他们的左序列右序列看在map中是否相同来染色

将他们存入左序列和右序列 合并的时候其实都是一样的..但是我为了省点内存写了两遍

首先我们要把左端点左右序列圈定在左块的范围内 然后再把右端点的左右序列圈定在右块的范围内

然后看左块的右序列颜色和右块左序列颜色是否相同 相同的话看是否属于同一个并查集 如果是那么答案在之前的基础上-1 最后处理完所有的情况 更新现在块的左序列&右序列

说几个坑点，我写程序时跳下的坑

tree[x].ls[i]=find(tree[tree[x].left].ls[i]),tree[x].rs[i]=find(tree[tree[x].right].rs[i]);

我一开始写的是搜索x的ls和rs了…

#include#define N 110000inline char gc(){ static char *S,*T,now[1<<16]; if (S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (S==T) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}int map[11][N],fa[11*N],cnt,num,n,m,q,root;struct node{ int l,r,left,right,sum,ls[11],rs[11];}tree[N<<2];struct node1{ int ls[11],rs[11],sum;};inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].sum=tree[l].sum+tree[r].sum; for (int i=1;i<=n;++i){ fa[tree[l].ls[i]]=tree[l].ls[i];fa[tree[l].rs[i]]=tree[l].rs[i]; fa[tree[r].ls[i]]=tree[r].ls[i];fa[tree[r].rs[i]]=tree[r].rs[i]; }int mid=tree[x].l+tree[x].r>>1; for (int i=1;i<=n;++i){ if (map[i][mid]==map[i][mid+1]){ int xx=find(tree[l].rs[i]),yy=find(tree[r].ls[i]); if (xx!=yy) fa[xx]=yy,tree[x].sum--; } } for (int i=1;i<=n;++i) tree[x].ls[i]=find(tree[tree[x].left].ls[i]),tree[x].rs[i]=find(tree[tree[x].right].rs[i]);} inline node1 update1(node1 a,node1 b,int mid){ node1 tmp;tmp.sum=a.sum+b.sum; for (int i=1;i<=n;++i){ fa[a.ls[i]]=a.ls[i];fa[a.rs[i]]=a.rs[i]; fa[b.ls[i]]=b.ls[i];fa[b.rs[i]]=b.rs[i]; } for (int i=1;i<=n;++i){ if (map[i][mid]==map[i][mid+1]){ int xx=find(a.rs[i]),yy=find(b.ls[i]); if (xx!=yy) fa[xx]=yy,tmp.sum--; } } for (int i=1;i<=n;++i) tmp.ls[i]=find(a.ls[i]),tmp.rs[i]=find(b.rs[i]); return tmp;}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r) { for (int i=1;i<=n;++i) if (map[i][l]==map[i-1][l]) tree[x].ls[i]=tree[x].rs[i]=tree[x].ls[i-1];else tree[x].ls[i]=tree[x].rs[i]=++cnt,tree[x].sum++; return; } int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}node1 query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r){ node1 tmp;tmp.sum=tree[x].sum; for (int i=1;i<=n;++i) tmp.ls[i]=tree[x].ls[i],tmp.rs[i]=tree[x].rs[i];return tmp; } int mid=tree[x].l+tree[x].r>>1; if (r<=mid) return query(tree[x].left,l,r); if (l>mid) return query(tree[x].right,l,r); return update1(query(tree[x].left,l,r),query(tree[x].right,l,r),mid);}void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d %d\n",tree[x].l,tree[x].r,tree[x].sum); if (tree[x].right) print(tree[x].right);}int main(){ freopen("cf.in","r",stdin); n=read();m=read();q=read(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) map[i][j]=read(); build(root,1,m);//print(root); for (int i=1;i<=q;++i){ int l=read(),r=read(); printf("%d\n",query(root,l,r).sum); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。