/* upsolve using persistent segment tree */
#include "rainbow.h"
#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define M 200000
#define L 100000
#define LG 18 /* LG = ceil(log2(M)) */
#define N_ ((L + 1) * 9 * (LG + 1))
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int cnt[1 + N_], ll[1 + N_], rr[1 + N_];
int update(int t, int l, int r, int i) {
static int _ = 1;
int t_ = _++;
cnt[t_] = cnt[t] + 1;
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
else
ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
}
return t_++;
}
int query_(int t, int l, int r, int ql, int qr) {
int m;
if (qr <= l || r <= ql || !t)
return 0;
if (ql <= l && r <= qr)
return cnt[t];
m = (l + r) / 2;
return query_(ll[t], l, m, ql, qr) + query_(rr[t], m, r, ql, qr);
}
int *jjj[N], kk[N], n, m;
void build(int *tt, int *ii, int *jj, int l) {
static char used[M];
int h, i, j, t;
for (h = 0; h < l; h++)
if (ii[h] < n)
kk[ii[h]]++;
for (i = 0; i < n; i++)
jjj[i] = (int *) malloc(kk[i] * sizeof *jjj[i]), kk[i] = 0;
for (h = 0; h < l; h++) {
i = ii[h], j = jj[h];
if (i < n && j < m)
jjj[i][kk[i]++] = j;
}
for (i = 0, t = 0; i < n; i++) {
for (h = 0; h < kk[i]; h++) {
j = jjj[i][h];
if (!used[j])
used[j] = 1, t = update(t, 0, m, j);
}
for (h = 0; h < kk[i]; h++) {
j = jjj[i][h];
used[j] = 0;
}
tt[i] = t;
}
for (i = 0; i < n; i++)
free(jjj[i]);
}
int ttv[N], tte1[N], tte2[N], ttf[N], imin, imax, jmin, jmax;
void init(int n_, int m_, int i_, int j_, int l, char *dd) {
static int ii[(L + 1) * 4], jj[(L + 1) * 4];
int h;
n = n_, m = m_, i_--, j_--;
imin = imax = i_, jmin = jmax = j_;
ii[0] = i_, jj[0] = j_;
for (h = 0; h < l; h++) {
if (dd[h] == 'N')
i_--;
else if (dd[h] == 'S')
i_++;
else if (dd[h] == 'W')
j_--;
else
j_++;
imin = min(imin, i_), imax = max(imax, i_), jmin = min(jmin, j_), jmax = max(jmax, j_);
ii[h + 1] = i_, jj[h + 1] = j_;
}
l++;
build(ttv, ii, jj, l);
for (h = 0; h < l; h++)
ii[l + h] = ii[h], jj[l + h] = jj[h] + 1;
build(tte1, ii, jj, l * 2);
for (h = 0; h < l; h++)
ii[l + h] = ii[h] + 1, jj[l + h] = jj[h];
build(tte2, ii, jj, l * 2);
for (h = 0; h < l; h++) {
ii[l + h] = ii[h], jj[l + h] = jj[h] + 1;
ii[l + l + h] = ii[h] + 1, jj[l + l + h] = jj[h];
ii[l + l + l + h] = ii[h] + 1, jj[l + l + l + h] = jj[h] + 1;
}
build(ttf, ii, jj, l * 4);
}
long long query(int *tt, int il, int ir, int jl, int jr) {
return il > ir || jl > jr ? 0 : (long long) (ir - il + 1) * (jr - jl + 1) - (query_(tt[ir], 0, m, jl, jr + 1) - (il == 0 ? 0 : query_(tt[il - 1], 0, m, jl, jr + 1)));
}
int colour(int il, int jl, int ir, int jr) {
long long v, e, f;
il--, jl--, ir--, jr--;
v = query(ttv, il, ir, jl, jr);
e = query(tte1, il, ir, jl + 1, jr) + query(tte2, il + 1, ir, jl, jr);
f = query(ttf, il + 1, ir, jl + 1, jr);
if (il < imin && imax < ir && jl < jmin && jmax < jr)
f++;
return v - e + f;
}
