#include "rainbow.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 400000 + 10;
const int INF = 1e9;
int n, m;
struct Point
{
int x, y;
friend bool operator < (const Point &a, const Point &b)
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
};
struct MergeSortTree
{
std::vector <int> tree[4*MAXN];
std::vector <Point> points;
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].push_back(points[l].y);
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
int lPtr = 0, rPtr = 0;
tree[node].reserve(r - l + 1);
for (int i = l ; i <= r ; ++i)
{
if (lPtr == tree[2*node].size())
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
continue;
}
if (rPtr == tree[2*node + 1].size())
{
tree[node].push_back(tree[2*node][lPtr++]);
continue;
}
if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
{
tree[node].push_back(tree[2*node][lPtr++]);
} else
{
tree[node].push_back(tree[2*node + 1][rPtr++]);
}
}
}
int countLess(int node, int value)
{
int l = -1, r = tree[node].size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (tree[node][mid] <= value) l = mid;
else r = mid;
}
return r;
}
int query(int l, int r, int node, int queryLPos, int queryRPos, int queryLVal, int queryRVal)
{
if (queryLPos <= l && r <= queryRPos)
{
return countLess(node, queryRVal) - countLess(node, queryLVal - 1);
}
int res = 0;
int mid = (l + r) / 2;
if (queryLPos <= mid) res += query(l, mid, 2*node, queryLPos, queryRPos, queryLVal, queryRVal);
if (mid + 1 <= queryRPos) res += query(mid + 1, r, 2*node + 1, queryLPos, queryRPos, queryLVal, queryRVal);
return res;
}
void build(const std::set <Point> &v)
{
points.reserve(v.size());
for (const auto &[x, y] : v)
{
points.push_back({x, y});
}
if (points.size()) build(0, (int)points.size() - 1, 1);
}
int searchLeftPos(int value)
{
int l = -1, r = points.size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (points[mid].x < value) l = mid;
else r = mid;
}
return r;
}
int searchRightPos(int value)
{
int l = -1, r = points.size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (points[mid].x <= value) l = mid;
else r = mid;
}
return l;
}
llong query(int fromX, int fromY, int toX, int toY)
{
llong res = 1LL * (toX - fromX + 1) * (toY - fromY + 1);
int left = searchLeftPos(fromX);
int right = searchRightPos(toX);
if (left <= right && fromY <= toY)
{
res -= query(0, (int)points.size() - 1, 1, left, right, fromY, toY);
}
return res;
}
};
MergeSortTree vertexTree;
MergeSortTree edgesRightTree;
MergeSortTree edgesDownTree;
MergeSortTree sidesTree;
std::set <Point> vertexPoints;
std::set <Point> edgesRightPoints;
std::set <Point> edgesDownPoints;
std::set <Point> sidesPoints;
std::set <Point> s;
int minX = INF;
int minY = INF;
int maxX;
int maxY;
void init(int R, int C, int sr, int sc, int M, char *S)
{
n = R;
m = C;
for (int i = 0 ; i < M ; ++i)
{
minX = std::min(minX, sr);
maxX = std::max(maxX, sr);
minY = std::min(minY, sc);
maxY = std::max(maxY, sc);
s.insert({sr, sc});
if (S[i] == 'N')
{
sr--;
} else if (S[i] == 'E')
{
sc++;
} else if (S[i] == 'S')
{
sr++;
} else if (S[i] == 'W')
{
sc--;
} else
{
assert(false);
}
}
s.insert({sr, sc});
minX = std::min(minX, sr);
maxX = std::max(maxX, sr);
minY = std::min(minY, sc);
maxY = std::max(maxY, sc);
for (const auto &[x, y] : s)
{
vertexPoints.insert({x, y});
edgesRightPoints.insert({x, y});
edgesDownPoints.insert({x, y});
sidesPoints.insert({x, y});
if (x > 1) edgesDownPoints.insert({x - 1, y});
if (y > 1) edgesRightPoints.insert({x, y - 1});
if (x > 1) sidesPoints.insert({x - 1, y});
if (y > 1) sidesPoints.insert({x, y - 1});
if (x > 1 && y > 1) sidesPoints.insert({x - 1, y - 1});
}
vertexTree.build(vertexPoints);
edgesRightTree.build(edgesRightPoints);
edgesDownTree.build(edgesDownPoints);
sidesTree.build(sidesPoints);
return;
}
int colour(int ar, int ac, int br, int bc)
{
llong res = 0;
res += vertexTree.query(ar, ac, br, bc);
res += sidesTree.query(ar, ac, br - 1, bc - 1);
if (ar < minX && ac < minY && br > maxX && bc > maxY) // another side
{
res++;
}
res -= edgesRightTree.query(ar, ac, br, bc - 1);
res -= edgesDownTree.query(ar, ac, br - 1, bc);
return res;
}
