Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags

Problem Statement:

Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags
Summary:
Given an integer matrix with size m x n with m <= 10, n <= 10^5, find the number of connected components in segment [l, r] of the matrix (i.e. rectangle (0, l) -> (m-1, r)). Two cells belong to the same connected component if they are adjacent (share the same edge) and have the same value.
There are q <= 10^5 such queries.

Solution:
A cool problem which can be solved using Segment Tree. This is made possible by the following observation: Consider two adjacent segments [l, m] and [m+1, r]. If we know the number of components on each segment, then we can iterate along the cells where the two segments meet to see if we can combine any adjacent components.

And hence, the number of components in [l, r] is given by the number of components in [l, m] + number of components in [m+1, r] - the number of components we combined.

To solve the problem then translates to building and querying a segment tree using the above strategy, tracking enough information to perform the merging. In my implementation, on each segment, I keep the component IDs of the cells to the left and right-end the segment.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int mat[100010][10];
int num_components[4*100010];
int group[4*100010][10][2];
int cur[4*100010][10][2];
int borrow[4*100010][10][2];
int n, m;
int next_id = 1;

int combine(int M, int p, int cur[4*100010][10][2], int group[4*100010][10][2]) {
  int left = 2*p;
  int right = 2*p+1;
  for (int i = 0; i < m; ++i) {
    cur[left][i][0] = group[left][i][0];
    cur[left][i][1] = group[left][i][1];
    cur[right][i][0] = group[right][i][0];
    cur[right][i][1] = group[right][i][1];
  }
  int unions = 0;
  for (int i = 0; i < m; ++i) {
    if (cur[left][i][1] == cur[right][i][0]) continue;
    if (mat[M][i] == mat[M+1][i]) {
      int c = cur[left][i][1];
      int d = cur[right][i][0];
      for (int j = 0; j < m; ++j) {
        for (int k = 0; k < 2; ++k) {
          if (cur[left][j][k] == c || cur[left][j][k] == d) {
            cur[left][j][k] = min(c,d);
          }
          if (cur[right][j][k] == c || cur[right][j][k] == d) {
            cur[right][j][k] = min(c,d);
          }
        }
      }
      ++unions;
    }
  }
  for (int i = 0; i < m; ++i) {
    group[p][i][0] = cur[left][i][0];
    group[p][i][1] = cur[right][i][1];
  }
  return unions;
}

void build(int L=0, int R=n-1, int p=1) {
  if (L == R) {
    num_components[p] = 1;
    group[p][0][0] = next_id++;
    for (int i = 1; i < m; ++i) {
      if (mat[L][i] == mat[L][i-1]) {
        group[p][i][0] = group[p][i-1][0];
      } else {
        group[p][i][0] = next_id++;
        num_components[p]++;
      }
    }
    for (int i = 0; i < m; ++i) {
      group[p][i][1] = group[p][i][0];
    }
    return;
  }
  int M = (L+R)/2;
  build(L, M, 2*p);
  build(M+1, R, 2*p+1);
  int unions = combine(M, p, cur, group);
  num_components[p] = num_components[2*p] + num_components[2*p+1] - unions;
}

int query(int S, int T, int L=0, int R=n-1, int p=1) {
  if (R<S || T<L) {
    return -1;
  }
  if (S<=L && R<=T) {
    for (int i = 0; i < m; ++i) {
      cur[p][i][0] = group[p][i][0];
      cur[p][i][1] = group[p][i][1];
    }
    return num_components[p];
  }
  int M = (L+R)/2;
  int left = query(S, T, L, M, 2*p);
  int right = query(S, T, M+1, R, 2*p+1);
  if (left >= 0 && right >= 0) {
    int unions = combine(M, p, borrow, cur);
    return left + right - unions;
  }
  int to_copy = 2*p;
  if (left == -1) {
    to_copy = 2*p+1;
  }
  for (int i = 0; i < m; ++i) {
    cur[p][i][0] = cur[to_copy][i][0];
    cur[p][i][1] = cur[to_copy][i][1];
  }
  return max(left, right);
}

int main(){
  int q;
  scanf("%d%d%d",&m,&n,&q);
  for (int i = 0;i <m;++i){
    for(int j = 0; j <n;++j){
      scanf("%d",&mat[j][i]);
    }
  }
  build();
  int L,R;
  for (int i = 0; i < q; ++i) {
    scanf("%d%d",&L,&R);
    L--; R--;
    printf("%d\n",query(L,R));
  }
  return 0;
}