(线段树+并查集) Codeforces Round #416 (Div. 2) E 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:

$\text{[math]}$

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 ≤ 10⁵) — 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 10⁶.

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

Output

Note

Partitioning on components for every segment from first test case:

$\text{[math]}$

线段树维护每个矩形边缘的情况，合并时利用并查集。

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <queue>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <vector>
 12 #include <stack>
 13 #define mp make_pair
 14 #define MIN(a,b) (a>b?b:a)
 15 #define rank rankk
 16 //#define MAX(a,b) (a>b?a:b)
 17 typedef long long ll;
 18 typedef unsigned long long ull;
 19 const int MAX=1e5+5;
 20 const ll INF=9223372036854775807;
 21 const int N=12;
 22 using namespace std;
 23 const int MOD=1e9+7;
 24 typedef pair<int,int> pii;
 25 const double eps=0.000000001;
 26 int par[MAX];
 27 int a[N][MAX];
 28 int n,m,q;
 29 int id[N<<1];
 30 int find(int x)
 31 {
 32     if(x==par[x])
 33         return x;
 34     return par[x]=find(par[x]);
 35 }
 36 void unite(int x,int y)
 37 {
 38     x=find(x);y=find(y);
 39     par[x]=y;
 40 }
 41 bool same(int x,int y)
 42 {
 43     return find(x)==find(y);
 44 }
 45 struct node
 46 {
 47     int l[N],r[N],sum;//l值在[1,n],r的值在[n+1,2n]
 48 }b[MAX<<2];
 49 void merge(node &lson,node &rson,node &rt,int lright,int rleft)
 50 {
 51     rt.sum=lson.sum+rson.sum;
 52     for(int i=1;i<=n;i++)
 53     {
 54         par[i]=lson.l[i];
 55         par[i+n]=lson.r[i];
 56         par[i+2*n]=rson.l[i]+2*n;
 57         par[i+3*n]=rson.r[i]+2*n;
 58     }
 59     for(int i=1;i<=n;i++)
 60     {
 61         if(a[i][lright]==a[i][rleft]&&!same(i+n,i+2*n))
 62         {
 63             --rt.sum;
 64             unite(i+n,i+2*n);
 65         }
 66     }
 67     for(int i=1;i<=4*n;i++)
 68     {
 69         par[i]=find(par[i]);
 70         id[par[i]]=-1;
 71     }
 72     for(int i=1;i<=n;i++)
 73     {
 74         if(id[par[i]]==-1)
 75             id[par[i]]=i;
 76         rt.l[i]=id[par[i]];
 77     }
 78     for(int i=3*n+1;i<=4*n;i++)
 79     {
 80         if(id[par[i]]==-1)
 81             id[par[i]]=i-2*n;
 82         rt.r[i-3*n]=id[par[i]];
 83     }
 84 }
 85 void build(int l,int r,int k)
 86 {
 87     if(l==r)
 88     {
 89         b[k].sum=0;
 90         for(int i=1;i<=n;i++)
 91         {
 92             if(i==1||a[i-1][l]!=a[i][l])
 93             {
 94                 b[k].l[i]=b[k].r[i]=i;
 95                 ++b[k].sum;
 96             }
 97             else
 98                 b[k].l[i]=b[k].r[i]=b[k].l[i-1];
 99         }
100         return ;
101     }
102     int mid=(l+r)/2;
103     build(l,mid,2*k);
104     build(mid+1,r,2*k+1);
105     merge(b[2*k],b[2*k+1],b[k],mid,mid+1);
106 }
107 void query(int ql,int qr,int l,int r,int k,node &ans)
108 {
109     if(l>=ql&&r<=qr)
110     {
111         ans=b[k];return;
112     }
113     int mid=(l+r)/2;
114     if(qr<=mid)
115         query(ql,qr,l,mid,2*k,ans);
116     else if(ql>mid)
117         query(ql,qr,mid+1,r,2*k+1,ans);
118     else
119     {
120         node p,q;
121         query(ql,qr,l,mid,2*k,p);
122         query(ql,qr,mid+1,r,2*k+1,q);
123         merge(p,q,ans,mid,mid+1);
124     }
125 }
126 int main()
127 {
128     int qs;
129     scanf("%d%d%d",&n,&m,&qs);
130     for(int i=1;i<=n;i++)
131         for(int j=1;j<=m;j++)
132             scanf("%d",&a[i][j]);
133     build(1,m,1);
134     node an;
135     int i;
136     for(i=1;i<=qs;i++)
137     {
138         int ls,rs;
139         scanf("%d%d",&ls,&rs);
140         query(ls,rs,1,m,1,an);
141         printf("%d
",an.sum);
142     }
143     return 0;
144 }