#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 60;
const int MAXL = 2*1e5 + 10;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
struct node{
int pref[2],suf[2],componentes,l0,r0,l1,r1,s0,s1;
node(int v0 = 0,int v1 = 0){
pref[0] = v0;pref[1] = v1;
suf[0] = v0;suf[1] = v1;
l0 = r0 = s0 = v0;
l1 = r1 = s1 = v1;
componentes = max(s0,s1);
}
node operator+(const node& other )const{
node novo;
novo.pref[0] = pref[0];novo.pref[1] = pref[1];
novo.suf[0] = other.suf[0];novo.suf[1] = suf[1];
novo.l0 = l0;novo.l1 = l1;
novo.r0 = other.r0;novo.r1 = other.r1;
novo.s0 = s0 + other.s0;
novo.s1 = s1 + other.s1;
novo.componentes = componentes + other.componentes;
if(suf[0] == 0 && suf[1] == 0){
if(other.pref[0] == 0 && other.pref[1] == 0){
}
else if(other.pref[0] == 1 && other.pref[1] == 0){
}
else if(other.pref[0] == 0 && other.pref[1] == 1){
}
else{
}
}
else if(suf[0] == 1 && suf[1] == 0){
if(other.pref[0] == 0 && other.pref[1] == 0){
}
else if(other.pref[0] == 1 && other.pref[1] == 0){
novo.componentes--;
novo.s0--;
}
else if(other.pref[0] == 0 && other.pref[1] == 1){
}
else{
novo.componentes--;
novo.s0--;
}
}
else if(suf[0] == 0 && suf[1] == 1){
if(other.pref[0] == 0 && other.pref[1] == 0){
}
else if(other.pref[0] == 1 && other.pref[1] == 0){
}
else if(other.pref[0] == 0 && other.pref[1] == 1){
novo.componentes--;
novo.s1--;
}
else{
novo.componentes--;
novo.s1--;
}
}
else{
if(other.pref[0] == 0 && other.pref[1] == 0){
}
else if(other.pref[0] == 1 && other.pref[1] == 0){
novo.componentes--;
novo.s0--;
}
else if(other.pref[0] == 0 && other.pref[1] == 1){
novo.componentes--;
novo.s1--;
}
else{
novo.componentes--;
novo.s0--;
novo.s1--;
}
}
return novo;
}
};
int matriz[MAXN][MAXN],tamx,tamy;
int tabela[3][MAXL];
int processado[MAXN][MAXN];
int lo_x,lo_y,hi_x,hi_y;
node seg[4*MAXN];
inline int valido(int x,int y){
return x >= lo_x && y >= lo_y && x <= hi_x && y <= hi_y && matriz[x][y] != 1;
}
void dfs(int x,int y){
if(processado[x][y]) return;
//printf("DFS %d %d\n",x,y);
processado[x][y] = 1;
for(int i = 0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(valido(nx,ny)) dfs(nx,ny);
}
}
void build(int pos,int left,int right){
//printf("P %d L %d R %d\n",pos,left,right);
if(left == right){
seg[pos] = node(1 - tabela[1][left],1 - tabela[2][left]);
return;
}
int mid = (left + right)/2;
build(2*pos,left,mid);
build(2*pos+1,mid+1,right);
seg[pos] = seg[2*pos] + seg[2*pos+1];
}
node query(int pos,int left,int right,int i,int j){
if(left >= i && right <= j){
return seg[pos];
}
int mid = (left+right)/2;
if(j <= mid) return query(2*pos,left,mid,i,j);
else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
else return query(2*pos,left,mid,i,j) + query(2*pos+1,mid+1,right,i,j);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
tamx = R;tamy= C;
if(tamx <= 50 && tamy <= 50){
matriz[sr][sc] = 1;
for(int vez = 0;vez<M;vez++){
if(S[vez] == 'N'){
//printf("N\n");
sr--;
}
else if(S[vez] == 'W'){
//printf("W\n");
sc--;
}
else if(S[vez] == 'S'){
//printf("S\n");
sr++;
}
else{
//printf("E\n");
sc++;
}
//printf("%d %d\n",sr,sc);
matriz[sr][sc] = 1;
}
//for(int i = 1;i<=tamx;i++){
// for(int j = 1;j<=tamy;j++){
// printf("%d",matriz[i][j]);
// }
// printf("\n");
//}
}
else{
tabela[sr][sc] = 1;
for(int vez = 0;vez<M;vez++){
if(S[vez] == 'N'){
//printf("N\n");
sr--;
}
else if(S[vez] == 'W'){
//printf("W\n");
sc--;
}
else if(S[vez] == 'S'){
//printf("S\n");
sr++;
}
else{
//printf("E\n");
sc++;
}
//printf("%d %d\n",sr,sc);
tabela[sr][sc] = 1;
}
build(1,1,tamy);
}
}
int colour(int ar, int ac, int br, int bc) {
if(tamx <= 50 && tamy <= 50){
memset(processado,0,sizeof(processado));
int total = 0;
lo_x = ar;lo_y = ac;
hi_x = br;hi_y = bc;
for(int i = ar;i<=br;i++){
for(int j = ac;j <= bc;j++){
if(matriz[i][j] == 1 || processado[i][j]) continue;
//printf("Componente nova\n");
dfs(i,j);
total++;
}
}
return total;
}
else{
node resposta = query(1,1,tamy,ac,bc);
if(ar == 1 && br == 1){
return resposta.s0;
}
else if(ar == 2 && br == 2){
return resposta.s1;
}
else{
return resposta.componentes;
}
}
}
