/**
Task: APIO17_rainbow (Land of the Rainbow Gold)
Link: https://oj.uz/problem/view/APIO17_rainbow
**/
#include <bits/stdc++.h>
#include "rainbow.h"
#define maxr 200005
#define maxc 200005
#define maxq 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int r, c;
struct persistent_tree {
vector<int> it, L, R, root;
int nt = 0;
int build(int lo, int hi) {
if (lo == hi) return ++nt;
int mid = (lo + hi) >> 1, cur = ++nt;
L[cur] = build(lo, mid);
R[cur] = build(mid+1, hi);
return cur;
}
void init(int r, int c, int m) {
root.assign(r+ 5, 0);
it.assign(22*(m+r+c) + 2*c + 5, 0);
L .assign(22*(m+r+c) + 2*c + 5, 0);
R .assign(22*(m+r+c) + 2*c + 5, 0);
root[0] = build(1, c);
}
int upd(int u, int oldver, int lo, int hi) {
if (lo == hi) {
it[++nt] = it[oldver] + 1;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
if (u <= mid) {
L[cur] = upd(u, L[oldver], lo, mid);
R[cur] = R[oldver];
} else {
L[cur] = L[oldver];
R[cur] = upd(u, R[oldver],mid+1,hi);
}
it[cur] = it[L[cur]] + it[R[cur]];
return cur;
}
int get(int u, int v, int r, int lo, int hi) {
if (u > hi || v < lo) return 0;
if (u <= lo && hi <= v) return it[r];
int mid = (lo + hi) >> 1;
return get(u, v, L[r], lo, mid) + get(u, v, R[r], mid+1, hi);
}
} tree_horizontal, tree_vertical, tree, tree_vertice;
int query_horizontal(int x, int y, int u, int v) {
if (x > u || y > v) return 0;
return tree_horizontal.get(y, v, tree_horizontal.root[u], 1, c) -
tree_horizontal.get(y, v, tree_horizontal.root[x-1], 1, c);
}
int query_vertical(int x, int y, int u, int v) {
if (x > u || y > v) return 0;
return tree_vertical.get(y, v, tree_vertical.root[u], 1, c+1) -
tree_vertical.get(y, v, tree_vertical.root[x-1], 1, c+1);
}
int query(int x, int y, int u, int v) {
if (x > u || y > v) return 0;
return tree.get(y, v, tree.root[u], 1, c)
- tree.get(y, v, tree.root[x-1], 1, c);
}
int query_vertice(int x, int y, int u, int v) {
if (x > u || y > v) return 0;
return tree_vertice.get(y, v, tree_vertice.root[u], 1, c+1)
- tree_vertice.get(y, v, tree_vertice.root[x-1],1, c+1);
}
int colour(int ar, int ac, int br, int bc) {
int E = query_horizontal(ar+1, ac, br, bc) +
query_vertical(ar, ac+1, br, bc)
+ 2 * (br-ar+2) + 4 * (br-ar+1)
+ 2 * (bc-ac+2) + 4 * (bc-ac+1);
int V = query_vertice(ar+1, ac+1, br, bc)
+ 4 * (br-ar+2) + 4 * (bc-ac+2) - 4;
int R = query(ar, ac, br, bc);
int C;
if (R == 0) C = 1;
else
C = (R - query(ar+1, ac+1, br-1, bc-1) > 0 ? 1 : 2);
int F = E - V + 1 + C;
R += 2 * (br-ar+1) + 2 * (bc-ac+1);
int A = F - (R+1);
return A;
}
//F = E - V + 1 + C
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
set<ii> hl, vl, p, vertices;
hl.insert(ii{sr+1, sc});
hl.insert(ii{sr , sc});
vl.insert(ii{sr, sc+1});
vl.insert(ii{sr, sc });
p.insert(ii{sr, sc});
vertices.insert(ii{sr, sc});
vertices.insert(ii{sr+1, sc});
vertices.insert(ii{sr, sc+1});
vertices.insert(ii{sr+1, sc+1});
tree_horizontal.init(r+1, c, M+1);
tree_vertical .init(r, c+1, M+1);
tree .init(r, c, M+1);
tree_vertice .init(r+1, c+1, M+1);
for (int i = 0; i < M; i++) {
char ch = S[i];
switch (ch) {
case 'N':
--sr;
break;
case 'W':
--sc;
break;
case 'S':
++sr;
break;
case 'E':
++sc;
break;
}
p.insert(ii{sr, sc});
hl.insert(ii{sr+1, sc});
hl.insert(ii{sr , sc});
vl.insert(ii{sr, sc+1});
vl.insert(ii{sr, sc });
vertices.insert(ii{sr, sc});
vertices.insert(ii{sr+1, sc});
vertices.insert(ii{sr, sc+1});
vertices.insert(ii{sr+1, sc+1});
}
int it;
it = 1;
for (auto [u, v] : hl) {
while (it <= u) {tree_horizontal.root[it] = tree_horizontal.root[it-1]; ++it;}
tree_horizontal.root[u] = tree_horizontal.upd(v, tree_horizontal.root[u], 1, c);
}
while (it <= r+1) {
tree_horizontal.root[it] = tree_horizontal.root[it-1];
++it;
}
it = 1;
for (auto [u, v] : vl) {
while (it <= u) {tree_vertical.root[it] = tree_vertical.root[it-1]; ++it;}
tree_vertical.root[u] = tree_vertical.upd(v, tree_vertical.root[u], 1, c+1);
}
while (it <= r) {
tree_vertical.root[it] = tree_vertical.root[it-1];
++it;
}
it = 1;
for (auto [u, v] : p) {
while (it <= u) {tree.root[it] = tree.root[it-1]; ++it;}
tree.root[u] = tree.upd(v, tree.root[u], 1, c);
}
while (it <= r) {
tree.root[it] = tree.root[it-1];
++it;
}
it = 1;
for (auto [u, v] : vertices) {
while (it <= u) {tree_vertice.root[it] = tree_vertice.root[it-1]; ++it;}
tree_vertice.root[u] = tree_vertice.upd(v, tree_vertice.root[u], 1, c+1);
}
while (it <= r+1) {
tree_vertice.root[it] = tree_vertice.root[it-1];
++it;
}
}
