Vladik and Entertaining Flags
Time Limit: 20 Sec Memory Limit: 512 MBDescription
n * m的矩形，每个格子上有一个数字代表颜色。
q次询问，询问[l, r]有几个连通块，若颜色相同并且连通则属于同一个连通块。
Input
输入第一行n,m,q。
然后一个n*m的矩形。 之后q行，每行两个整数l，r。Output
输出q行，对于每个询问输出答案。
Sample 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
Sample Output
6 7 3 4
HINT
1 ≤ n ≤ 10, 1 ≤ m, q ≤ 1e5， 1 ≤ l ≤ r ≤ m
Solution
我们运用线段树，线段树一个节点i维护这个点表示的[L, R]。
具体维护Li列~Ri列的连通块个数，Li列连通信息，Ri列连通信息，Li列编号，Ri列编号。
连通信息指的是n个点的连通关系，用一个[10]存下来即可。
我们现在考虑如何合并两个区间。
合并的时候，我们先cnt = 两个区间cnt之和，然后考虑左区间的右端信息 以及 右区间的左端信息。
如果有两个相同的值属于不同连通块，就把它们连通起来，修改一下信息，然后cnt--。显然用并查集处理连通即可。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long s64; 10 11 const int ONE = 1000005; 12 const int MOD = 1e9 + 7; 13 14 int get() 15 { 16 int res = 1, Q = 1; char c; 17 while( (c = getchar()) < 48 || c > 57) 18 if(c == '-') Q = -1; 19 if(Q) res = c - 48; 20 while( (c = getchar()) >= 48 && c <= 57) 21 res = res * 10 + c - 48; 22 return res * Q; 23 } 24 25 int n, m, Q; 26 int col[11][ONE]; 27 int l, r; 28 29 int fat[ONE], total = 0; 30 int Find(int x) 31 { 32 if(fat[x] == x) return x; 33 return fat[x] = Find(fat[x]); 34 } 35 36 int Un(int x, int y) 37 { 38 int f1 = Find(x), f2 = Find(y); 39 if(f1 != f2) return fat[f1] = f2, 1; 40 return 0; 41 } 42 43 struct power 44 { 45 int val; 46 int l[11], lid; 47 int r[11], rid; 48 friend power operator +(power a, power b) 49 { 50 power c; 51 c.val = a.val + b.val; 52 c.lid = a.lid, c.rid = b.rid; 53 54 for(int i = 1; i <= n; i++) 55 fat[a.l[i]] = a.l[i], fat[a.r[i]] = a.r[i], 56 fat[b.l[i]] = b.l[i], fat[b.r[i]] = b.r[i]; 57 58 for(int i = 1; i <= n; i++) 59 if(col[i][a.rid] == col[i][b.lid]) 60 c.val -= Un(a.r[i], b.l[i]); 61 62 for(int i = 1; i <= n; i++) 63 c.l[i] = Find(a.l[i]), c.r[i] = Find(b.r[i]); 64 65 return c; 66 } 67 }Node[ONE]; 68 69 void Build(int i, int l, int r) 70 { 71 if(l == r) 72 { 73 Node[i].lid = Node[i].rid = l; 74 for(int j = 1; j <= n; j++) 75 if(col[j - 1][l] != col[j][l]) 76 Node[i].l[j] = Node[i].r[j] = ++total, Node[i].val++; 77 else 78 Node[i].l[j] = Node[i].r[j] = Node[i].l[j - 1]; 79 return; 80 } 81 int mid = l + r >> 1; 82 Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r); 83 Node[i] = Node[i << 1] + Node[i << 1 | 1]; 84 } 85 86 power Query(int i, int l, int r, int L, int R) 87 { 88 if(L <= l && r <= R) return Node[i]; 89 90 int mid = l + r >> 1; 91 if(!(mid + 1 <= R)) return Query(i << 1, l, mid, L, R); 92 else if(!(L <= mid)) return Query(i << 1 | 1, mid + 1, r, L, R); 93 else return Query(i << 1, l, mid, L, R) + Query(i << 1 | 1, mid + 1, r, L ,R); 94 } 95 96 int main() 97 { 98 n = get(); m = get(); Q = get(); 99 for(int i = 1; i <= n; i++)100 for(int j = 1; j <= m; j++)101 col[i][j] = get();102 Build(1, 1, m);103 104 while(Q--)105 {106 l = get(), r = get();107 power res = Query(1, 1, m, l, r);108 printf("%d\n", res.val);109 }110 111 }