#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 2e5 + 10;
set < pair < int, int > > nodes, ver_edges, hor_edges, river;
int min_x = inf, max_x = -inf, min_y = inf, max_y = -inf;
struct fenwick_2d
{
map < int, int > data[maxn];
vector < int > vec[maxn], pref[maxn];
void build()
{
for (int i = 0; i < maxn; i ++)
{
vec[i].push_back(0);
pref[i].push_back(0);
for (pair < int, int > cur : data[i])
{
//if (i == 2)
{
//cout << cur.first << " ------- " << cur.second << " " << vec[i].back().second << endl;
}
int new_val = pref[i].back() + cur.second;
vec[i].push_back(cur.first);
pref[i].push_back(new_val);
}
}
/**for (int i = 0; i < 10; i ++)
{
cout << "step " << i << endl;
for (int cur : vec[i])
cout << cur << " ";
cout << endl;
}*/
}
void add(int pos, int val)
{
for (int i = pos; i < maxn; i += (i & -i))
{
data[i][val] ++;
}
}
int bin_search(int idx, int val)
{
int lf = 0, rf = (int)(vec[idx].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (vec[idx][mf] <= val)
lf = mf + 1;
else
rf = mf - 1;
}
return lf;
}
int query(int pos, int lb, int rb)
{
///cout << "QUERY " << pos << " " << lb << " " << rb << endl;
int ans = 0;
for (int i = pos; i > 0; i -= (i & -i))
{
int left = bin_search(i, lb - 1), right = bin_search(i, rb);
//cout << "left right " << left << " " << right << " " << vec[i][left].second << " :: " << vec[i][right].second << endl;
ans = ans + (pref[i][right - 1 ]- pref[i][left - 1]);
}
//cout << "Ans " << ans << endl;
return ans;
}
int range_query(int from, int to, int lb, int rb)
{
return query(to, lb, rb) - query(from - 1, lb, rb);
}
};
fenwick_2d fen_river;
fenwick_2d fen_nodes;
fenwick_2d fen_hor;
fenwick_2d fen_ver;
void add_node(int x, int y)
{
nodes.insert({x, y});
}
void add_hor_edge(int x, int y)
{
hor_edges.insert({x, y});
}
void add_ver_edge(int x, int y)
{
ver_edges.insert({x, y});
}
void add_river(int x, int y)
{
add_node(x, y);
add_node(x, y + 1);
add_node(x + 1, y);
add_node(x + 1, y + 1);
add_hor_edge(x, y);
add_hor_edge(x + 1, y);
add_ver_edge(x, y);
add_ver_edge(x, y + 1);
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
river.insert({x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
add_river(sr, sc);
for (int i = 0; i < M; i ++)
{
if (S[i] == 'N')
sr --;
else if (S[i] == 'S')
sr ++;
else if (S[i] == 'W')
sc --;
else if (S[i] == 'E')
sc ++;
else assert(false);
add_river(sr, sc);
}
for (pair < int, int > cur : river)
{
fen_river.add(cur.first, cur.second);
}
for (pair < int, int > cur : nodes)
{
fen_nodes.add(cur.first, cur.second);
}
for (pair < int, int > cur : hor_edges)
{
fen_hor.add(cur.first, cur.second);
}
for (pair < int, int > cur : ver_edges)
{
fen_ver.add(cur.first, cur.second);
}
fen_river.build();
fen_nodes.build();
fen_hor.build();
fen_ver.build();
}
int query_nodes(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : nodes)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_hor_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : hor_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_ver_edges(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : ver_edges)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int query_river(int ar, int ac, int br, int bc)
{
int cnt = 0;
for (pair < int, int > cur : river)
{
if (cur.first >= ar && cur.first <= br &&
cur.second >= ac && cur.second <= bc)
cnt ++;
}
return cnt;
}
int colour(int ar, int ac, int br, int bc)
{
int V = fen_nodes.range_query(ar + 1, br, ac + 1, bc) + (br - ar + 2) * 2 + (bc - ac) * 2;
int E = 0;
E = E + fen_hor.range_query(ar + 1, br, ac, bc) + (bc - ac + 1) * 2;
E = E + fen_ver.range_query(ar, br, ac + 1, bc) + (br - ar + 1) * 2;
int C = 1;
if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
C ++;
/// V + F = E + C + 1
/// F = E - V + C + 1
int F = E - V + C - fen_river.range_query(ar, br, ac, bc); //query_river(ar, ac, br, bc);
///cout << "V " << V << " E " << E << " C " << C << endl;
//cout << "Faces " << F << endl;
///exit(0);
return F;
}
