#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 PersistentSegmentTree
{
public:
void copy(int node)
{
e.push_back( e[node] );
d.push_back( d[node] );
sum.push_back( sum[node] );
}
int update(int node, int l, int r, int i)
{
int newNode = ++cnt;
copy( node );
if( l == r )
{
sum[newNode]++;
return newNode;
}
int m = ( l + r )/2;
if( i <= m )
{
int aux = update( e[newNode] , l , m , i );
e[newNode] = aux;
}
else
{
int aux = update( d[newNode] , m + 1 , r , i );
d[newNode] = aux;
}
sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];
return newNode;
}
void updateRoot() { root.push_back( root.back() ); }
void update(int y)
{
if( y < 1 || C < y ) return;
int r = update( root.back() , 1 , C , y );
root.back() = r;
}
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;
}
int query(int x1, int y1, int x2, int y2)
{
int ans = query( root[x2] , 1 , C , y1 , y2 );
ans -= query( root[x1 - 1] , 1 , C , y1 , y2 );
return ans;
}
PersistentSegmentTree() : cnt(1)
{
e.resize( 2 , 0 ); d.resize( 2 , 0 );
sum.resize( 2 , 0 ); root.resize( 1 , 1 );
}
protected:
int cnt;
vector<int> e, d;
vector<int> sum, root;
};
int minY, maxY;
int minX, maxX;
vector<int> sweep[4][MAXN];
PersistentSegmentTree SEG[4];
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 );
sweep[0][x].push_back( y );
sweep[1][x].push_back( y );//Hor
sweep[2][x].push_back( y );
if( !inside( x , y - 1 ) )
sweep[1][x].push_back( y - 1 );
if( !inside( x - 1 , y ) )
sweep[2][x - 1].push_back( y );
sweep[3][x].push_back( y );
if( !inside( x - 1 , y ) )
sweep[3][x - 1].push_back( y );
if( !inside( x , y - 1 ) && !inside( x + 1 , y - 1 ) )
sweep[3][x].push_back( y - 1 );
if( !inside( x , y - 1 ) && !inside( x - 1 , y ) && !inside( x - 1 , y - 1 ) )
sweep[3][x - 1].push_back( y - 1 );
}
for(int i = 1 ; i <= R ; i++)
{
for(int k = 0 ; k < 4 ; k++)
{
SEG[k].updateRoot();
while( !sweep[k][i].empty() )
{
SEG[k].update( sweep[k][i].back() );
sweep[k][i].pop_back();
}
}
}
}
int colour(int ar, int ac, int br, int bc)
{
lli N = br - ar + 1;
lli M = bc - ac + 1;
lli qtdVertices = N*M - SEG[0].query( ar , ac , br , bc );
lli qtdEdges = 2*N*M - N - M;
qtdEdges -= SEG[1].query( ar , ac , br , bc - 1 );
qtdEdges -= SEG[2].query( ar , ac , br - 1 , bc );
lli qtdFaces = (N - 1)*(M - 1);
qtdFaces -= SEG[3].query( ar , ac , br - 1 , bc - 1 );
lli ans = qtdVertices - qtdEdges + qtdFaces;
if( ar < minX && maxX < br && ac < minY && maxY < bc )
ans++;
return ans;
}
