#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l;
map<ll,pair<ll,ll>> positions; //{position, {nextpos, bucketstart}}
//num cameras to protrude outside bucket, right coord of bucketwidth
unordered_map<ll,ll> poscnt;
vector<ll> ind2coord;
vector<ll> bucketx; //x coords of buckets + INF coord
ll INF = 1e9+1;
//denotes end of sequence
ll sizev;
ll qcount = 0;
void updateBucket(int ind){
//cout<<"updating "<<ind<<" "<<bucketx[ind]<<'\n';
//generate bucketstart, numcameras, nextpos from positions
auto it = positions.lower_bound(bucketx[ind+1]);
ll ptr = ind;
do {
it = prev(it);
//cout<<it->first<<'\n';
//process
if (it->first<bucketx[ptr]){
return;
}
ll rightedge = it->first+l; //upper_bound
if (rightedge<bucketx[ptr+1]){
auto ub = positions.upper_bound(rightedge);
if (ub==positions.end()){
(it->second).first = 1;
(it->second).second = INF;
} else if (ub->first>=bucketx[ptr+1]){
(it->second).first = 1;
(it->second).second = rightedge;
} else {
(it->second).first = (ub->second).first+1;
(it->second).second = (ub->second).second;
}
} else {
(it->second).first = 1;
(it->second).second = rightedge;
}
} while (it!=positions.begin());
//assert(ind==0||0==1);
}
void genBuckets(){
//cout<<"generating\n";
bucketx.clear();
ll len = 0;
sizev = sqrt(positions.size());
bucketx.push_back(-1);
for (auto p : positions){
if (len==0){
bucketx.push_back(p.first);
}
len++;
if (len==sizev){
len=0;
}
}
bucketx.push_back(INF);
/*for (ll i : bucketx){
//cout<<i<<", ";
}//cout<<"\n";*/
for (ll i = bucketx.size()-2; i>=0; i--){
updateBucket(i);
}
}
void init(int N, int L, int X[]) {
n = N;l=L;
ind2coord = vector<ll>(X,X+n);
for (ll i = 0; i<n; i++){
if (poscnt.find(X[i])==poscnt.end()){
poscnt[X[i]]++;
positions[X[i]]={INF,INF};
} else {
poscnt[X[i]]++;
}
}
genBuckets();
}
int update(int i, int y) {
//cout<<"update "<<i<<" "<<y<<'\n';
//remove thing at index i
ll oldplace = ind2coord[i];
ind2coord[i]=y;
ll newplace = y;
poscnt[oldplace]--;
if (poscnt[oldplace]==0){
positions.erase(oldplace);
}
if (poscnt[newplace]==0){
positions[newplace]={INF,INF};
}
poscnt[newplace]++;
qcount++;
if (qcount%sizev==0){
qcount=0;
genBuckets();
} else {
//cout<<oldplace<<" "<<newplace<<'\n';
updateBucket(upper_bound(bucketx.begin(),bucketx.end(),oldplace)-bucketx.begin()-1);
updateBucket(upper_bound(bucketx.begin(),bucketx.end(),newplace)-bucketx.begin()-1);
}
ll cnt = 0;
auto ptr = positions.begin();
while (ptr!=positions.end()){
cnt+=ptr->second.first;
ptr = positions.upper_bound(ptr->second.second);
}
assert(cnt<INF);
return cnt;
}
