#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define L 18
#define N_ (1 << L)
#define M (42424242)
int sum[M], ll[M], rr[M];
int node(int k = 0) {
static int _ = 1;
sum[_] = sum[k];
ll[_] = ll[k], rr[_] = rr[k];
return _++;
}
int build_(int l, int r) {
int v = node(), m;
if (l < r) {
m = (l + r) / 2;
ll[v] = build_(l, m);
rr[v] = build_(m + 1, r);
}
return v;
}
int update(int v, int l, int r, int i) {
int v_ = node(v), m;
sum[v_]++;
if (l < r) {
m = (l + r) / 2;
if (i <= m)
ll[v_] = update(ll[v], l, m, i);
else
rr[v_] = update(rr[v], m + 1, r, i);
}
return v_;
}
int query_(int v, int l, int r, int ql, int qr) {
int m;
if (qr < l || ql > r)
return 0;
if (ql <= l && qr >= r)
return sum[v];
m = (l + r) / 2;
return query_(ll[v], l, m, ql, qr) + query_(rr[v], m + 1, r, ql, qr);
}
struct tree {
vector<int> pp[N + 1];
int xx[N + 1];
void add(int i, int j) {
pp[i].push_back(j);
}
void build() {
for (int i = 1; i <= N; i++) {
xx[i] = xx[i - 1];
sort(pp[i].begin(), pp[i].end());
pp[i].erase(unique(pp[i].begin(), pp[i].end()), pp[i].end());
for (int j : pp[i - 1])
xx[i] = update(xx[i], 1, N, j);
}
}
int query(int i, int j, int i_, int j_) {
if (i_ > j_)
return 0;
return query_(xx[j + 1], 1, N, i_, j_) - query_(xx[i], 1, N, i_, j_);
}
} st0, st1, st2, st3;
void add(int i, int j) {
st0.add(i, j);
st0.add(i + 1, j);
st0.add(i, j + 1);
st0.add(i + 1, j + 1);
st1.add(i, j);
st1.add(i + 1, j);
st2.add(i, j);
st2.add(i, j + 1);
st3.add(i, j);
}
int mx_i, mn_i, mx_j, mn_j;
void init(int n, int m, int si, int sj, int k, char *s) {
add(si, sj);
mx_i = mn_i = si;
mx_j = mn_j = sj;
for (int i = 0; i < k; i++) {
if (s[i] == 'N')
si--;
if (s[i] == 'E')
sj++;
if (s[i] == 'S')
si++;
if (s[i] == 'W')
sj--;
add(si, sj);
mx_i = max(mx_i, si);
mn_i = min(mn_i, si);
mx_j = max(mx_j, sj);
mn_j = min(mn_j, sj);
}
st0.build();
st1.build();
st2.build();
st3.build();
}
int colours(int i, int j, int i_, int j_) {
int E = st1.query(i + 1, i_, j, j_) + st2.query(i, i_, j + 1, j_);
int V = st0.query(i + 1, i_, j + 1, j_);
int R = st3.query(i, i_, j, j_);
int C = (i >= mn_i || i_ <= mx_i || j >= mn_j || j_ <= mx_j ? 1 : 2);
return E - V + C - R;
}
/*
int main() {
static char s[N + 1];
int n, m, k, q, si, sj;
scanf("%d%d%d%d", &n, &m, &k, &q);
scanf("%d%d", &si, &sj);
if (k > 0)
scanf("%s", s);
init(n, m, si, sj, k, s);
while (q--) {
int i, j, i_, j_;
scanf("%d%d%d%d", &i, &j, &i_, &j_);
printf("%d\n", colours(i, j, i_, j_));
}
}
*/
Compilation message
/usr/bin/ld: /tmp/ccGJ8SAg.o: in function `main':
grader.cpp:(.text.startup+0x167): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status
