811E - Vladik and Entertaining Flags

This is 811E's solution by g1n0st

In the contest I didn't pass this problem because I'm very rubbish.

After reading the question, I thought it is very difficult at first. And then I found:

• N only in range of 10

• Every matrices of requests are from [1, l] to [r, n]

So it means, if we use Segment tree to maintain the main matrix (1, 1, n, m) , we needn't usd two dimension Segment tree but common. For every nodes (l, r) on the tree we define two arrayes L [1, n] and R [1..n] describing the situations of the sequence's beginning and ending, and a integer number to record sequence's value, then we can use union-find sets to maintain two sequences.

It works in O(MlogM * N)