/*
ID: varunra2
LANG: C++
TASK: elephants
*/
// cp ~/SNIPPETS/Template/testing/*
// gen.cpp and build with IORun
// create brute.cpp and build with IORun
// this runs 5 random tests against a with checkts against brute
// ./test.sh 5 a
// any failed tests will be saved under data/failed*{inp,out,oac} pattern. .oac
// is output of brute, .out is output of program, .inp is output of gen
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n, l;
const int BLOCK = 400;
multiset<PII> st;
VI vals;
struct block {
VI pnts;
int siz;
VI dp1; // how many blocks for suffix starting at i, ending at pnts.size()?
VI dp2; // where does the optimal solution held at dp1[i] end?
void init() {
sort(all(pnts));
siz = sz(pnts);
dp1.resize(siz);
dp2.resize(siz);
}
void calc() {
init();
int p1 = siz - 1;
for (int i = siz - 1; i >= 0; i--) {
while ((pnts[p1] - pnts[i]) > l) p1--;
if (p1 == siz - 1) {
dp1[i] = 1;
dp2[i] = pnts[i] + l;
} else {
dp1[i] = dp1[p1 + 1] + 1;
dp2[i] = dp2[p1 + 1];
}
}
}
void ins(int x) {
pnts.PB(x);
calc();
}
void del(int x) {
VI cop;
trav(xx, pnts) {
if (xx == x) continue;
cop.PB(xx);
}
pnts = cop;
calc();
}
PII get(int x) {
// how many to cover rest of this block starting at x
// where would it end at
auto it = upper_bound(all(pnts), x);
if (it == pnts.end()) {
return MP(0, x);
}
int ind = it - pnts.begin();
return MP(dp1[ind], dp2[ind]);
}
void pr(int i = -1) {
debug("printing block", i);
debug("pnts", pnts);
debug("dp1", dp1);
debug("dp2", dp2);
}
};
vector<block> blocks;
void rebuild(bool done = true) {
// we are rebuilding blocks
VI pnts;
pnts = vals;
blocks.clear();
sort(all(pnts));
VI cur;
st.clear();
for (int i = 0; i < sz(pnts); i++) {
cur.PB(pnts[i]);
st.insert(MP(pnts[i], sz(blocks)));
if (sz(cur) == BLOCK) {
block nw;
nw.pnts = cur;
nw.calc();
cur.clear();
blocks.PB(nw);
}
}
if (!cur.empty()) {
block nw;
nw.pnts = cur;
nw.calc();
cur.clear();
blocks.PB(nw);
}
}
void ins(int x) {
debug("we got an insertation - reeeeeeeeeeeeeeeeeee");
debug(x);
// what block are we in?
auto it = st.lower_bound(MP(x, -1));
if(it == st.end()) {
int ind = sz(blocks) - 1;
blocks[ind].ins(x);
st.insert(MP(x, ind));
return;
}
auto xx = *it;
blocks[xx.y].ins(x);
st.insert(MP(x, xx.y));
debug(st);
debug(xx);
}
void del(int x) {
debug("we got a deletion - wooooooooooooooooooooooo");
debug(x);
auto xx = *st.lower_bound(MP(x, -1));
blocks[xx.y].del(x);
st.erase(st.lower_bound(MP(x, -1)));
debug(st);
}
int qry() {
debug("we got a query - uh oh");
int ret = 0;
int ind = -1;
for (int i = 0; i < sz(blocks); i++) {
auto x = blocks[i].get(ind);
ret += x.x;
ind = x.y;
debug(ret, ind);
}
return ret;
}
int lst;
void init(int N, int L, int X[]) {
n = N;
l = L;
for (int i = 0; i < n; i++) {
vals.PB(X[i]);
}
rebuild(false); // first time building
lst = qry();
}
int cnt = 0;
int update(int i, int y) {
debug("we got an update asdfasfsdfasfasdfasfsadfasdfa");
int cur = vals[i];
vals[i] = y;
// debug(vals);
del(cur);
ins(y);
cnt++;
if (cnt % BLOCK == 0) {
rebuild();
}
int ret = qry();
assert(abs(ret - lst) <= 1);
lst = ret;
return ret;
}
// int main() {
// #ifndef ONLINE_JUDGE
// freopen("elephants.in", "r", stdin);
// freopen("elephants.out", "w", stdout);
// #endif
// cin.sync_with_stdio(0);
// cin.tie(0);
// string barrier =
// "=======================================================================";
// debug(barrier);
// int n, l, q;
// cin >> n >> l >> q;
// int x[n];
// for (int i = 0; i < n; i++) {
// cin >> x[i];
// }
// init(n, l, x);
// debug(qry());
// while (q--) {
// int i, y;
// cin >> i >> y;
// debug(i, y);
// int correct;
// cin >> correct;
// int ret = update(i, y);
// debug(ret);
// debug(correct);
// debug(ret == correct);
// assert(ret == correct);
// }
// return 0;
// }
