#include "rainbow.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int logo = 19;
const int off = 1 << logo;
const int treesiz = off << 1;
const int inf = 0x3f3f3f3f;
struct node {
node *l, *r;
int val;
node() {
l = r = nullptr;
val = 0;
}
};
typedef node* pnode;
inline pnode L(pnode tren) {
if (tren == nullptr) return nullptr;
return tren->l;
}
inline pnode R(pnode tren) {
if (tren == nullptr) return nullptr;
return tren->r;
}
inline int value(pnode tren) {
if (tren == nullptr) return 0;
return tren->val;
}
void update(pnode tren, pnode prev, int x, int l, int r, int val) {
if (l > x || r < x) return;
if (x == l && x == r) {
tren->val = value(prev) + val;
return;
}
int mid = (l + r) / 2;
if (x <= mid) {
tren->l = new node();
tren->r = R(prev);
update(tren->l, L(prev), x, l, mid, val);
} else {
tren->r = new node();
tren->l = L(prev);
update(tren->r, R(prev), x, mid + 1, r, val);
}
tren->val = value(tren->l) + value(tren->r);
}
int query(pnode tren, int a, int b, int l, int r) {
if (tren == nullptr) return 0;
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tren->val;
int mid = (l + r) / 2;
return query(tren->l, a, b, l, mid) + query(tren->r, a, b, mid + 1, r);
}
struct tournament {
pnode root[maxn];
int kol;
tournament() {
kol = 0;
for (int i = 0; i < maxn; i++)
root[i] = nullptr;
}
void add(vector< int > &v) {
pnode ptr = root[kol];
kol++;
for (int tren : v) {
pnode nw = new node();
update(nw, ptr, tren, 0, off - 1, 1);
ptr = nw;
}
root[kol] = ptr;
}
int query(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return 0;
return ::query(root[x2], y1, y2, 0, off - 1) - ::query(root[x1 - 1], y1, y2, 0, off - 1);
}
} vert, faces, edgesx, edgesy;
void insert(set< pair<int, int> > &s, tournament &tour) {
auto iter = s.begin();
for (int i = 1; i < maxn; i++) {
vector< int > v;
while (iter != s.end() && iter->X == i) {
v.push_back(iter->Y);
iter++;
}
tour.add(v);
}
}
int minx = inf, maxx = 0, miny = inf, maxy = 0;
void init(int R, int C, int sr, int sc, int M, char *S) {
set< pair<int, int> > s;
s.insert({sr, sc});
minx = maxx = sr;
miny = maxy = 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 sc++;
s.insert({sr, sc});
minx = min(minx, sr);
maxx = max(maxx, sr);
miny = min(miny, sc);
maxy = max(maxy, sc);
}
auto iter = s.begin();
set< pair<int, int> > ac;
set< pair<int, int> > xv, yv;
for (int i = 1; i < maxn; i++) {
vector< int > v;
while (iter != s.end() && iter->X == i) {
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++)
ac.insert({iter->X + x, iter->Y + y});
xv.insert(*iter); xv.insert({iter->X + 1, iter->Y});
yv.insert(*iter); yv.insert({iter->X, iter->Y + 1});
v.push_back(iter->Y);
iter++;
}
vert.add(v);
}
insert(ac, faces);
insert(xv, edgesx);
insert(yv, edgesy);
}
int colour(int ar, int ac, int br, int bc) {
llint v = (llint)(br - ar + 1) * (bc - ac + 1) - vert.query(ar, ac, br, bc);
llint f = (llint)(br - ar) * (bc - ac) - faces.query(ar + 1, ac + 1, br, bc);
llint e = (llint)(br - ar + 1) * (bc - ac) + (llint)(br - ar) * (bc - ac + 1);
e -= edgesx.query(ar + 1, ac, br, bc);
e -= edgesy.query(ar, ac + 1, br, bc);
if (ar < minx && br > maxx && ac < miny && bc > maxy) f++;
//printf("debug: %lld %lld %lld\n", v, e, f);
assert(v + f - e >= 0);
return v + f - e;
}
