#include "elephants.h"
#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1.5e5;
int n, L;
struct TElephant {
int id, x;
int f, xDest;
inline bool operator < (const TElephant &b) const
{
return x < b.x || (x == b.x && id < b.id); // if x equals, compare by id
}
};
vector<vector<TElephant> > a;
int pos[N];
const int BLOCK_SIZE = 600;
void Calc(vector<TElephant> &seg)
{
auto itR = prev(seg.end()), itL = itR;
itL->f = 0, itL->xDest = itL->x;
while (itL != seg.begin())
{
--itL;
while (itR != itL && itL->x + L < prev(itR)->x) itR = prev(itR);
if (itL->x + L < itR->x)
{
itL->f = itR->f + 1;
itL->xDest = itR->xDest;
}
else
itL->f = 0, itL->xDest = itL->x;
}
}
pair<int, int> arr[N];
void Rebuild()
{
int m = 0;
for (const auto &seg: a)
for (const auto &e: seg)
arr[m++] = {e.id, e.x};
a.clear();
vector<TElephant> cur;
for (int i = 0; i < n; ++i)
{
cur.push_back({arr[i].first, arr[i].second, 0, arr[i].second});
if (cur.size() >= BLOCK_SIZE || i == n - 1)
{
Calc(cur);
a.push_back(move(cur));
cur.clear();
}
}
}
void init(int numElephants, int camWidth, int X[])
{
n = numElephants;
L = camWidth;
vector<TElephant> sentinel;
for (int i = 0; i < n; ++i)
{
pos[i] = X[i];
sentinel.push_back({i, X[i], 0, 0});
}
a.push_back(move(sentinel));
Rebuild();
}
const int STACK_SIZE = 400;
int countQuery = 0;
int GetAns()
{
int ans = 0, curX = a.begin()->begin()->x;
for (auto i = a.begin(); i != a.end(); ++i)
if (prev(i->end())->x >= curX) // if segment contain current X
{
auto it = lower_bound(i->begin(), i->end(), curX, [](TElephant p, int q) {
return p.x < q;
});
ans += it->f + 1; // jump inner-segment, then to new segment
curX = it->xDest + L + 1;
}
return ans;
}
int update(int idx, int y)
{
int x = pos[idx];
TElephant old_ele {idx, x, 0, 0};
TElephant new_ele {idx, y, 0, 0};
// erase idx from old position
{
auto i = lower_bound(a.begin(), a.end(), old_ele, [](const vector<TElephant> &p, TElephant q) {
return p.back() < q;
});
vector<TElephant> leftSeg;
for (auto it = i->begin(); it != i->end(); ++it)
if (it->id == idx)
{
// cut segment into 2 parts
leftSeg = vector<TElephant>(i->begin(), it);
i->erase(i->begin(), next(it));
break;
}
if (i->empty()) i = a.erase(i);
if (!leftSeg.empty())
{
Calc(leftSeg);
a.insert(i, move(leftSeg));
}
}
// insert idx to new position
if (a.empty())
a.push_back(vector<TElephant>(1, new_ele));
else
{
auto i = lower_bound(a.begin(), a.end(), new_ele, [](const vector<TElephant> &p, TElephant q) {
return p.back() < q;
});
if (i != a.end())
{
for (auto it = i->begin(); it != i->end(); ++it)
if (new_ele < *it)
{
i->insert(it, new_ele);
break;
}
}
else
{
--i;
i->push_back(new_ele);
}
Calc(*i);
}
pos[idx] = y;
++countQuery;
if (countQuery >= STACK_SIZE) Rebuild(), countQuery = 0;
return GetAns();
}
