#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_)]); }