#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5, inf=2e5;
int mxr, mnr, mxc, mnc;
struct persist
{
set<int> s[nx];
struct node
{
int sm;
node *l, *r;
node(int sm=0): sm(sm), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &k)
{
k=new node();
if (l==r) return;
int md=(l+r)/2;
build(l, md, k->l);
build(md+1, r, k->r);
}
void update(int l, int r, pnode &k, pnode t, int idx)
{
k=new node(*t);
if (l==r) return k->sm++, void();
int md=(l+r)/2;
if (idx<=md) update(l, md, k->l, t->l, idx);
else update(md+1, r, k->r, t->r, idx);
k->sm=k->l->sm+k->r->sm;
}
void init()
{
build(1, inf, rt[0]);
for (int i=1; i<=inf; i++)
{
rt[i]=rt[i-1];
for (auto idx:s[i]) update(1, inf, rt[i], rt[i], idx);
}
}
int query(int l, int r, pnode k, int ql, int qr)
{
if (qr<l||r<ql||qr<ql) return 0;
if (ql<=l&&r<=qr) return k->sm;
int md=(l+r)/2;
return query(l, md, k->l, ql ,qr)+query(md+1, r, k->r, ql, qr);
}
int querysquare(int ar, int ac, int br, int bc)
{
return query(1, inf, rt[br], ac, bc)-query(1, inf, rt[ar-1], ac, bc);
}
} edgver, edghor, vertex, river;
void addnode(int a, int b)
{
edgver.s[a].insert(b);
edgver.s[a].insert(b+1);
edghor.s[a].insert(b);
edghor.s[a+1].insert(b);
vertex.s[a].insert(b);
vertex.s[a].insert(b+1);
vertex.s[a+1].insert(b);
vertex.s[a+1].insert(b+1);
river.s[a].insert(b);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
mxr=mnr=sr;
mxc=mnc=sc;
addnode(sr, sc);
for (int i=0; i<M; i++)
{
if (S[i]=='N') sr--;
if (S[i]=='S') sr++;
if (S[i]=='W') sc--;
if (S[i]=='E') sc++;
addnode(sr, sc);
mxr=max(mxr, sr);
mnr=min(mnr, sr);
mxc=max(mxc, sc);
mnc=min(mnc, sc);
}
edgver.init();
edghor.init();
vertex.init();
river.init();
}
int colour(int ar, int ac, int br, int bc) {
int edg=edgver.querysquare(ar, ac+1, br, bc)+edghor.querysquare(ar+1, ac, br, bc);
int ver=vertex.querysquare(ar+1, ac+1, br, bc);
int comp=(mnr<=ar||mxr>=br||mnc<=ac||mxc>=bc)?1:2;
int face=1+comp-ver+edg;
int rv=river.querysquare(ar, ac, br, bc);
return face-rv-1;
}
