#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 2e5 + 10;
struct node
{
int lc, rc, sum;
node()
{
lc = rc = -1;
sum = 0;
}
};
struct persistent_segment_tree
{
node tree[30 * maxn];
int roots[maxn], last_used;
vector < int > data[maxn];
int update(int root, int left, int right, int pos, int val)
{
int new_node = ++ last_used;
if (root != -1)
tree[new_node] = tree[root];
if (left == right)
{
tree[new_node].sum += val;
return new_node;
}
int mid = (left + right) / 2;
if (pos <= mid)
tree[new_node].lc = update(tree[new_node].lc, left, mid, pos, val);
else
tree[new_node].rc = update(tree[new_node].rc, mid + 1, right, pos, val);
tree[new_node].sum = 0;
if (tree[new_node].lc != -1)
tree[new_node].sum += tree[tree[new_node].lc].sum;
if (tree[new_node].rc != -1)
tree[new_node].sum += tree[tree[new_node].rc].sum;
return new_node;
}
int query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft || root == -1)
return 0;
if (left >= qleft && right <= qright)
return tree[root].sum;
int mid = (left + right) / 2;
return query(tree[root].lc, left, mid, qleft, qright) +
query(tree[root].rc, mid + 1, right, qleft, qright);
}
void init(set < pair < int, int > > &my_set)
{
last_used = 0;
for (pair < int, int > cur : my_set)
{
data[cur.first].push_back(cur.second);
}
roots[0] = -1;
for (int i = 1; i < maxn; i ++)
{
roots[i] = roots[i - 1];
for (int cur : data[i])
{
roots[i] = update(roots[i], 1, maxn - 1, cur, 1);
}
}
}
int query_rectangle(int lb, int rb, int dw, int up)
{
return query(roots[rb], 1, maxn - 1, dw, up) -
query(roots[lb - 1], 1, maxn - 1, dw, up);
}
};
persistent_segment_tree river_tree;
persistent_segment_tree nodes_tree;
persistent_segment_tree ver_tree;
persistent_segment_tree hor_tree;
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();*/
river_tree.init(river);
nodes_tree.init(nodes);
ver_tree.init(ver_edges);
hor_tree.init(hor_edges);
}
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 = nodes_tree.query_rectangle(ar + 1, br, ac + 1, bc);///fen_nodes.range_query(ar + 1, br, ac + 1, bc) ;
int E = 0;
E = E + hor_tree.query_rectangle(ar + 1, br, ac, bc);
E = E + ver_tree.query_rectangle(ar, br, ac + 1, bc);
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 - river_tree.query_rectangle(ar, br, ac, bc);///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;
}
