#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
struct Node {
int val = 0;
Node *lc = nullptr;
Node *rc = nullptr;
};
int sz;
Node *root = nullptr;
void Pull(Node* &n) {
n->val = 0;
if (n->lc != nullptr) n->val += n->lc->val;
if (n->rc != nullptr) n->val += n->rc->val;
}
void Update(Node* &n, int tl, int tr, int p, int x) {
if (n == nullptr) n = new Node();
if (tl == tr) return void(n->val += x);
int mid = (tl + tr) / 2;
if (p <= mid) {
Update(n->lc, tl, mid, p, x);
} else {
Update(n->rc, mid + 1, tr, p, x);
}
return Pull(n);
}
int Query(Node* &n, int tl, int tr, int l, int r) {
if (n == nullptr) return 0;
if (r < tl || tr < l || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return n->val;
int mid = (tl + tr) / 2;
return Query(n->lc, tl, mid, l, r) +
Query(n->rc, mid + 1, tr, l, r);
}
public:
SegmentTree() {}
SegmentTree(int sz) : sz(sz) {}
void Update(int p, int x) {
return Update(root, 0, sz, p, x);
}
int Query(int l, int r) {
return Query(root, 0, sz, l, r);
}
};
class RangeTree {
private:
struct Node {
SegmentTree seg;
Node *lc = nullptr;
Node *rc = nullptr;
Node(int sz) : seg(sz) {}
};
int sx, sy;
Node *root = nullptr;
void Update(Node* &n, int tl, int tr, int p, int q, int x) {
if (n == nullptr) n = new Node(sy);
n->seg.Update(q, x);
if (tl == tr) return;
int mid = (tl + tr) / 2;
if (p <= mid) {
Update(n->lc, tl, mid, p, q, x);
} else {
Update(n->rc, mid + 1, tr, p, q, x);
}
}
int Query(Node* &n, int tl, int tr, int l, int r, int d, int u) {
if (n == nullptr) return 0;
if (r < tl || tr < l || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return n->seg.Query(d, u);
int mid = (tl + tr) / 2;
return Query(n->lc, tl, mid, l, r, d, u) +
Query(n->rc, mid + 1, tr, l, r, d, u);
}
public:
RangeTree() {}
RangeTree(int sx, int sy) : sx(sx), sy(sy) {}
void Update(int p, int q, int x) {
return Update(root, 0, sx, p, q, x);
}
int Query(int l, int r, int d, int u) {
return Query(root, 0, sx, l, r, d, u);
}
};
// V - E + F = 2
// Vertices = 4 suares points aroud river cells
// Edges = borders around river cells
// Faces = land components + number of river cells
RangeTree river_cells; // keeps V - E + F, scaled by 2
int minr, maxr, minc, maxc;
void init(int R, int C, int sr, int sc, int M, char *S) {
river_cells = RangeTree(2 * R + 5, 2 * C + 5);
map<pair<int, int>, int> tobe;
auto Update = [&](int x, int y) { // cell (x, y) is a river cell
// Vertices
tobe[{2 * x - 1, 2 * y - 1}] = 1;
tobe[{2 * x - 1, 2 * y + 1}] = 1;
tobe[{2 * x + 1, 2 * y - 1}] = 1;
tobe[{2 * x + 1, 2 * y + 1}] = 1;
// Edges
tobe[{2 * x - 1, 2 * y}] = -1;
tobe[{2 * x + 1, 2 * y}] = -1;
tobe[{2 * x, 2 * y - 1}] = -1;
tobe[{2 * x, 2 * y + 1}] = -1;
// Faces
tobe[{2 * x, 2 * y}] = 1;
};
minr = maxr = sr;
minc = maxc = sc;
Update(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++;
Update(sr, sc);
minr = min(minr, sr);
minc = min(minc, sc);
maxr = max(maxr, sr);
maxc = max(maxc, sc);
}
minr--;
maxr++;
minc--;
maxc++;
for (auto p : tobe) {
river_cells.Update(p.first.first, p.first.second, p.second);
}
}
int colour(int ar, int ac, int br, int bc) {
ar = max(ar, minr);
ac = max(ac, minc);
br = min(br, maxr);
bc = min(bc, maxc);
return 1 + (ar == minr && ac == minc && br == maxr && bc == maxc)
- river_cells.Query(2 * ar, 2 * br, 2 * ac, 2 * bc);
}
