#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
const int MAXN = 200010;
int dx[] = { -1 , 1 , 0 , 0 };
int dy[] = { 0 , 0 , -1 , 1 };
char dir[] = { 'N' , 'S' , 'W' , 'E' };
int R, C;
class SparseSegmentTree
{
public:
void create()
{
e.push_back( 0 );
d.push_back( 0 );
sum.push_back( 0 );
}
int getLeft(int node)
{
if( e[node] == 0 )
e[node] = ++cnt, create();
return e[node];
}
int getRight(int node)
{
if( d[node] == 0 )
d[node] = ++cnt, create();
return d[node];
}
void update(int node, int l, int r, int i, int v)
{
if( i < l || r < i ) return;
if( l == r )
{
sum[node] += v;
return;
}
int m = ( l + r )/2;
if( i <= m ) update( getLeft(node) , l , m , i , v );
else update( getRight(node) , m + 1 , r , i , v );
sum[node] = sum[ e[node] ] + sum[ d[node] ];
}
int query(int node, int l, int r, int i, int j)
{
if( node == 0 ) return 0;
if( j < l || r < i ) return 0;
if( i <= l && r <= j ) return sum[node];
int m = ( l + r )/2;
int sumLeft = query( e[node] , l , m , i , j );
int sumRight = query( d[node] , m + 1 , r , i , j );
return sumLeft + sumRight;
}
SparseSegmentTree() : cnt(1) { create(); create(); }
protected:
int cnt;
vector<int> sum;
vector<int> e, d;
};
class FenwickTree
{
public:
void update(int x, int y, int v)
{
for( ; x != 0 && x <= R ; x += x & -x)
SEG[x].update( 1 , 1 , C , y , v );
}
int query(int x, int y1, int y2)
{
int ans = 0;
for( ; x > 0 ; x -= x & -x)
ans += SEG[x].query( 1 , 1 , C , y1 , y2 );
return ans;
}
int query(int x1, int y1, int x2, int y2)
{
int ans = query( x2 , y1 , y2 );
ans -= query( x1 - 1 , y1 , y2 );
return ans;
}
protected:
SparseSegmentTree SEG[MAXN];
};
int minY, maxY;
int minX, maxX;
FenwickTree faces;
FenwickTree vertices;
FenwickTree edgesVert, edgesHor;
set<pii> river;
int conv(char a)
{
for(int i = 0 ; i < 4 ; i++)
if( a == dir[i] ) return i;
}
bool inside(int x, int y) { return ( river.find( { x , y } ) ) != river.end(); }
void init(int r, int c, int sr, int sc, int M, char *S)
{
R = r; C = c;
river.insert( { sr , sc } );
for(int i = 0 ; i < M ; i++)
{
int d = conv( S[i] );
sr += dx[d]; sc += dy[d];
river.insert( { sr , sc } );
}
maxX = -MAXN; minX = MAXN;
maxY = -MAXN; minY = MAXN;
for(auto it = river.begin() ; it != river.end() ; it++)
{
int x = it->first;
int y = it->second;
maxX = max( maxX , x ); minX = min( minX , x );
maxY = max( maxY , y ); minY = min( minY , y );
vertices.update( x , y , 1 );
edgesHor.update( x , y , 1 );
edgesVert.update( x , y , 1 );
if( !inside( x - 1 , y ) )
edgesVert.update( x - 1 , y , 1 );
if( !inside( x , y - 1 ) )
edgesHor.update( x , y - 1 , 1 );
faces.update( x , y , 1 );
if( !inside( x - 1 , y ) )
faces.update( x - 1 , y , 1 );
if( !inside( x , y - 1 ) && !inside( x + 1 , y - 1 ) )
faces.update( x , y - 1 , 1 );
if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
faces.update( x - 1 , y - 1 , 1 );
}
}
int colour(int ar, int ac, int br, int bc)
{
lli N = br - ar + 1;
lli M = bc - ac + 1;
lli qtdVertices = N*M - vertices.query( ar , ac , br , bc );
lli qtdEdges = 2*N*M - N - M;
qtdEdges -= edgesHor.query( ar , ac , br , bc - 1 );
qtdEdges -= edgesVert.query( ar , ac , br - 1 , bc );
lli qtdFaces = (N - 1)*(M - 1);
qtdFaces -= faces.query( ar , ac , br - 1 , bc - 1 );
lli ans = qtdVertices - qtdEdges + qtdFaces;
if( ar < minX && maxX < br && ac < minY && maxY < bc )
ans++;
return ans;
}
