Vladik and Entertaining Flags

Time Limit: 20 Sec Memory Limit: 512 MB

Description

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000005;
const int MOD = 1e9 + 7;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

int n, m, Q;
int col[11][ONE];
int l, r;

int fat[ONE], total = 0;
int Find(int x)
{
    if(fat[x] == x) return x;
    return fat[x] = Find(fat[x]);
}

int Un(int x, int y)
{
    int f1 = Find(x), f2 = Find(y);
    if(f1 != f2) return fat[f1] = f2, 1;
    return 0;
}

struct power
{
    int val;
    int l[11], lid;
    int r[11], rid;
    friend power operator +(power a, power b)
    {
        power c;
        c.val = a.val + b.val;
        c.lid = a.lid, c.rid = b.rid;

        for(int i = 1; i <= n; i++)
            fat[a.l[i]] = a.l[i], fat[a.r[i]] = a.r[i],
        fat[b.l[i]] = b.l[i], fat[b.r[i]] = b.r[i];

        for(int i = 1; i <= n; i++)
            if(col[i][a.rid] == col[i][b.lid])
                c.val -= Un(a.r[i], b.l[i]);

        for(int i = 1; i <= n; i++)
            c.l[i] = Find(a.l[i]), c.r[i] = Find(b.r[i]);

        return c;
    }
}Node[ONE];

void Build(int i, int l, int r)
{
    if(l == r)
    {
        Node[i].lid = Node[i].rid = l;
        for(int j = 1; j <= n; j++)
            if(col[j - 1][l] != col[j][l])
                Node[i].l[j] = Node[i].r[j] = ++total, Node[i].val++;
        else
            Node[i].l[j] = Node[i].r[j] = Node[i].l[j - 1];
        return;
    }
    int mid = l + r >> 1;
    Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r);
    Node[i] = Node[i << 1] + Node[i << 1 | 1];
}

power Query(int i, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return Node[i];

    int mid = l + r >> 1;
    if(!(mid + 1 <= R)) return Query(i << 1, l, mid, L, R);
    else if(!(L <= mid)) return Query(i << 1 | 1, mid + 1, r, L, R);
    else return Query(i << 1, l, mid, L, R) + Query(i << 1 | 1, mid + 1, r, L ,R);
}

int main()
{
    n = get();    m = get();    Q = get();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            col[i][j] = get();
    Build(1, 1, m);

    while(Q--)
    {
        l = get(), r = get();
        power res = Query(1, 1, m, l, r);
        printf("%d\n", res.val);
    }

}