#include "elephants.h"
#define N 150000
#define Q 150000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N * 2], n, d;
int compare(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : i - j; }
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], _, u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_(), ii[_] = i;
return _++;
}
int first(int u) {
return ll[u] == 0 ? u : first(ll[u]);
}
int last(int u) {
return rr[u] == 0 ? u : last(rr[u]);
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = compare(ii[u], i);
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int pp[N * 2];
void link(int i, int j) {
pp[i] = j;
}
int depth(int i) {
int d = 0;
while (i >= 0) {
if (i < n)
d++;
i = pp[i];
}
return d;
}
void init(int n_, int d_, int *xx_) {
static int ii[N * 2];
int i;
n = n_, d = d_;
for (i = 0; i < n; i++)
xx[i] = xx_[i], xx[n + i] = xx[i] + d;
for (i = 0; i < n * 2; i++)
ii[i] = i;
sort(ii, 0, n * 2);
for (i = 0; i < n * 2; i++) {
link(ii[i], i + 1 == n * 2 ? -1 : (ii[i] < n ? ii[i] + n : ii[i + 1]));
u_ = merge(u_, node(ii[i]));
}
}
int update(int i, int x) {
int u, v, p;
split(u_, n + i), v = u_, p = l_ ? ii[last(l_)] : -1;
if (p >= n)
link(p, r_ ? ii[first(r_)] : -1);
pp[n + i] = -1;
u_ = merge(l_, r_);
split(u_, i), u = u_, p = l_ ? ii[last(l_)] : -1;
if (p >= n)
link(p, r_ ? ii[first(r_)] : -1);
u_ = merge(l_, r_);
xx[i] = x, xx[n + i] = xx[i] + d;
split(u_, n + i), p = l_ ? ii[last(l_)] : -1;
if (p >= n)
link(p, n + i);
pp[n + i] = r_ ? ii[first(r_)] : -1;
u_ = merge(merge(l_, v), r_);
split(u_, i), p = l_ ? ii[last(l_)] : -1;
if (p >= n)
link(p, i);
u_ = merge(merge(l_, u), r_);
return depth(ii[first(u_)]);
}
