#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int _R = 2e5 + 5;
struct PSTRangeSum {
struct Node {
int idx, val;
Node* left;
Node* right;
Node(int _idx) : idx(_idx), val(0), left(nullptr), right(nullptr) {}
};
int dim[2];
vector<set<int>> temp;
vector<Node*> roots;
PSTRangeSum(int _dim1, int _dim2) {
dim[0] = _dim1;
dim[1] = _dim2;
temp.assign(_dim1 + 1, set<int>());
}
void add(int x, int y) {
temp[x].insert(y);
}
void build() {
roots.push_back(new Node(0));
for (int i = 1; i <= dim[0]; i++) {
roots.push_back(new Node(i));
roots[i]->val = roots[i-1]->val;
roots[i]->left = roots[i-1]->left;
roots[i]->right = roots[i-1]->right;
//cout << i << ": ";
for (auto j : temp[i]) {
//cout << j << " ";
update(roots[i], roots[i-1], 1, dim[1], i, j);
}
//cout << '\n';
}
}
void update(Node* cur, Node* prv, int l, int r, int x, int idx) {
if (l == r) {
cur->val++;
return;
}
int m = (l + r) >> 1;
if (idx <= m) {
if (!cur->left || cur->left->idx != x) {
cur->left = new Node(x);
if (prv && prv->left) {
cur->left->val = prv->left->val;
}
}
if (!cur->right || cur->right->idx != x) {
if (prv) {
cur->right = prv->right;
}
}
if (prv) {
update(cur->left, prv->left, l, m, x, idx);
} else {
update(cur->left, nullptr, l, m, x, idx);
}
} else {
if (!cur->right || cur->right->idx != x) {
cur->right = new Node(x);
if (prv && prv->right) {
cur->right->val = prv->right->val;
}
}
if (!cur->left || cur->left->idx != x) {
if (prv) {
cur->left = prv->left;
}
}
if (prv) {
update(cur->right, prv->right, m+1, r, x, idx);
} else {
update(cur->right, nullptr, m+1, r, x, idx);
}
}
cur->val = 0;
if (cur->left) {cur->val += cur->left->val;}
if (cur->right) {cur->val += cur->right->val;}
}
void traverse(Node* cur, int depth) {
if (!cur) return;
string s(depth, ' ');
cout << s;
printf("%d %d\n", cur->idx, cur->val);
traverse(cur->left, depth+1);
traverse(cur->right, depth+1);
}
int query(Node* cur, int l, int r, int ql, int qr) {
if (!cur) return 0;
if (l > qr || ql > r) return 0;
if (ql <= l && r <= qr) return cur->val;
int m = (l + r) >> 1;
return query(cur->left, l, m, ql, qr) + query(cur->right, m+1, r, ql, qr);
}
int rangequery(int x1, int x2, int y1, int y2) {
return query(roots[x2], 1, dim[1], y1, y2) - query(roots[x1-1], 1, dim[1], y1, y2);
}
} vertices(_R, _R), edgesH(_R, _R), edgesV(_R, _R), rivers(_R, _R);
int minR, maxR, minC, maxC;
void insert(int x, int y) {
vertices.add(x, y);
vertices.add(x+1, y);
vertices.add(x, y+1);
vertices.add(x+1, y+1);
edgesH.add(x, y);
edgesH.add(x+1, y);
edgesV.add(x, y);
edgesV.add(x, y+1);
rivers.add(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
insert(sr, sc);
minR = maxR = sr;
minC = maxC = 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++;}
insert(sr, sc);
minR = min(minR, sr);
maxR = max(maxR, sr);
minC = min(minC, sc);
maxC = max(maxC, sc);
}
vertices.build();
edgesH.build();
edgesV.build();
rivers.build();
//cout << "Vertices\n";
//for (int i = 0; i <= maxR+1; i++) {vertices.traverse(vertices.roots[i], 0);}
}
int colour(int ar, int ac, int br, int bc) {
int E = edgesH.rangequery(ar+1, br, ac, bc) + edgesV.rangequery(ar, br, ac+1, bc);
int V = vertices.rangequery(ar+1, br, ac+1, bc);
int R = rivers.rangequery(ar, br, ac, bc);
int C = 1 + (int)(ar < minR && br > maxR && ac < minC && bc > maxC);
//printf("%d %d %d %d\n", E, V, R, C);
return E - V - R + C;
}
