#include "rainbow.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
constexpr int mxN = 2e5 + 5;
struct SegmentTree {
struct Node {
int v = 0, l = 0, r = 0;
};
std::vector<int> points[mxN];
std::vector<Node> info = {Node(), Node()};
int roots[mxN + 1];
int copy(int k) {
info.emplace_back(info[k]);
return info.size() - 1;
}
void add_point(int x, int y) {
points[x].push_back(y);
}
void build() {
roots[0] = 1;
for (int i = 0; i < mxN; i++) {
roots[i + 1] = roots[i];
std::sort(points[i].begin(), points[i].end());
points[i].erase(std::unique(points[i].begin(), points[i].end()), points[i].end());
for (int y : points[i]) {
roots[i + 1] = update(roots[i + 1], 0, mxN, y, 1);
}
}
}
int update(int k, int l, int r, int p, int v) {
int id = copy(k);
info[id].v += v;
if (r - l == 1) return id;
int m = (l + r) / 2;
if (p < m) {
int left = update(info[id].l, l, m, p, v);
info[id].l = left;
} else {
int right = update(info[id].r, m, r, p, v);
info[id].r = right;
}
return id;
}
int query(int k, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return info[k].v;
int m = (l + r) / 2;
int ans = 0;
if (m > ql) {
ans += query(info[k].l, l, m, ql, qr);
}
if (m < qr) {
ans += query(info[k].r, m, r, ql, qr);
}
return ans;
}
int query(int x1, int y1, int x2, int y2) {
if (x1 >= x2 || y1 >= y2) return 0;
return query(roots[x2], 0, mxN, y1, y2) - query(roots[x1], 0, mxN, y1, y2);
}
} rivers, vertices, edges_ho, edges_ve;
void add_river(int x, int y) {
dbg(x, y);
rivers.add_point(x, y);
vertices.add_point(x, y);
vertices.add_point(x + 1, y);
vertices.add_point(x, y + 1);
vertices.add_point(x + 1, y + 1);
edges_ho.add_point(x, y);
edges_ho.add_point(x + 1, y);
edges_ve.add_point(x, y);
edges_ve.add_point(x, y + 1);
}
int mn_x, mx_x, mn_y, mx_y;
void init(int R, int C, int sr, int sc, int M, char *S) {
mn_x = mx_x = sr;
mn_y = mx_y = sc;
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 sc++;
add_river(sr, sc);
mn_x = std::min(mn_x, sr);
mx_x = std::max(mx_x, sr);
mn_y = std::min(mn_y, sc);
mx_y = std::max(mx_y, sc);
}
rivers.build();
vertices.build();
edges_ho.build();
edges_ve.build();
}
int colour(int ar, int ac, int br, int bc) {
dbg(ar, ac, br, bc);
int E = edges_ho.query(ar + 1, ac, br + 1, bc + 1) + edges_ve.query(ar, ac + 1, br + 1, bc + 1);
E += (br - ar + 1 + bc - ac + 1) * 2;
int V = vertices.query(ar + 1, ac + 1, br + 1, bc + 1);
V += (br - ar) * 2 + (bc - ac + 2) * 2;
int R = rivers.query(ar, ac, br + 1, bc + 1);
int C = (ar < mn_x && br > mx_x && ac < mn_y && bc > mx_y) ? 2 : 1;
dbg(E, V, R, C);
return E - V + C - R;
}
