#include "rainbow.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
const int MAXN = 2e5 + 7;
using ll = long long;
struct Fenwick2D { // ah wait defapt pot face doar niste cautari binare
std::set<std::pair<int, int>> cells;
std::vector<int> ys[MAXN + 1];
void add(int x, int y) {
if (cells.count({x, y})) { // sa am grija sa nu inserez aceeasi pozitie de mai multe ori
return;
}
cells.insert({x, y});
x++;
for (int i = x; i <= MAXN; i += i & -i) {
ys[i].push_back(y);
}
}
void build() {
for (int i = 1; i <= MAXN; i++) {
ys[i].push_back(0);
ys[i].push_back(MAXN + 7);
std::sort(ys[i].begin(), ys[i].end());
}
}
int query(int x, int y) {
x++;
int ret = 0;
for (int i = x; i > 0; i -= i & -i) {
ret += std::upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
}
return ret;
}
int query(int x1, int y1, int x2, int y2) {
return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
};
namespace {
int minX, maxX, minY, maxY;
Fenwick2D vert, horizontalEdges, verticalEdges, boxes;
};
void init(int R, int C, int sr, int sc, int M, char *S) {
int x = sr, y = sc;
minX = R + 1;
minY = C + 1;
maxX = 0;
maxY = 0;
auto add = [&](int x, int y) {
minX = std::min(minX, x);
maxX = std::max(maxX, x);
minY = std::min(minY, y);
maxY = std::max(maxY, y);
vert.add(x, y);
horizontalEdges.add(x, y);
horizontalEdges.add(x, y - 1);
verticalEdges.add(x, y);
verticalEdges.add(x - 1, y);
boxes.add(x, y);
boxes.add(x, y - 1);
boxes.add(x - 1, y);
boxes.add(x - 1, y - 1);
};
add(x, y);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') {
x--;
} else if (S[i] == 'S') {
x++;
} else if (S[i] == 'W') {
y--;
} else {
y++;
}
add(x, y);
}
vert.build();
horizontalEdges.build();
verticalEdges.build();
boxes.build();
}
int colour(int x1, int y1, int x2, int y2) {
ll V = (ll) (x2 - x1 + 1) * (y2 - y1 + 1) - vert.query(x1, y1, x2, y2);
ll E = 0;
E += (ll) (x2 - x1 + 1) * (y2 - y1) - horizontalEdges.query(x1, y1, x2, y2 - 1);
E += (ll) (x2 - x1) * (y2 - y1 + 1) - verticalEdges.query(x1, y1, x2 - 1, y2);
ll F = (ll) (x2 - x1) * (y2 - y1) - boxes.query(x1, y1, x2 - 1, y2 - 1);
F++;
if (x1 < minX && maxX < x2 && y1 < minY && maxY < y2) {
F++;
}
// V + F = E + C + 1 (cred)
return V + F - E - 1;
}
