#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
///Land cells is a vertex, and two adjacent land cells
///All faces formed are 2x2 squares, where all 4 cells are land cells
///Except possibly when the entire rectangle surrounds the rivers, then there is 1 more additonal face on the inside
///No. of components = V - E + F (We ignore the outer face as a face)
///As the V, E and F are large, we instead use a segment tree to count how many vertices, edges and faces are absent.
const int N = 200002;
int totalRivers;
struct segment{
vector<int> tree[2*N+5];
inline void update(int i, int v){
tree[i+N].push_back(v);
}
inline void getReady(){
for(int i = N;i < 2*N;i++){
sort(tree[i].begin(),tree[i].end());
tree[i].erase(unique(tree[i].begin(),tree[i].end()),tree[i].end());
}
for(int i = N-1;i > 0;i--){ ///basically merge sort
tree[i] = vector<int>(tree[i<<1].size()+tree[i<<1|1].size());
merge(tree[i<<1].begin(),tree[i<<1].end(), tree[i<<1|1].begin(),tree[i<<1|1].end(),tree[i].begin());
}
}
inline int query(int l, int r, int x, int y){
int ans = 0;
for(l += N, r += (N+1);l < r;l >>= 1, r >>= 1){
if(l&1){
ans += upper_bound(tree[l].begin(),tree[l].end(),y) - lower_bound(tree[l].begin(),tree[l].end(),x);
l++;
}
if(r&1){
r--;
ans += upper_bound(tree[r].begin(),tree[r].end(),y) - lower_bound(tree[r].begin(),tree[r].end(),x);
}
}
return ans;
}
} vertices, horizontal, vertical, faces;
///Vertices store vertices which are rivers
///Edges store edges which are not between two land cells, horizontal is (r,c) to (r,c+1), vertical is (r,c) to (r+1,c)
///Squares store which group of 4 sqaures with at least 1 river. It stores the top left corner (r,c)
void addRiver(int r, int c){
vertices.update(r,c);
horizontal.update(r,c-1);
horizontal.update(r,c);
vertical.update(c,r-1);
vertical.update(c,r);
faces.update(r-1,c-1);
faces.update(r,c-1);
faces.update(r-1,c);
faces.update(r,c);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
addRiver(sr,sc);
for(int i = 0;i < M;i++){
if(S[i] == 'N') sr--;
else if(S[i] == 'S') sr++;
else if(S[i] == 'E') sc++;
else sc--;
addRiver(sr,sc);
}
vertices.getReady(); horizontal.getReady(); vertical.getReady(); faces.getReady();
totalRivers = vertices.query(0,N-1,0,N-1);
}
int colour(int T, int L, int B, int R) {
long long H = B - T + 1, W = R - L + 1;
long long V = H * W - vertices.query(T,B,L,R);
long long E = (H-1)*W + (W-1)*H - horizontal.query(T,B,L,R-1) - vertical.query(L,R,T,B-1);
long long F = (H-1)*(W-1) - faces.query(T,B-1,L,R-1);
if(vertices.query(T+1,B-1,L+1,R-1) == totalRivers) F++;
return V - E + F;
}
