#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define db(v) //cerr << #v << ": " << v << " ";
#define dbln(v) //cerr << #v << ": " << v << endl;
// const int B_QTD = 120, B_SZ = 1255, Q = 400, MAXN = 150010;
// const int B_QTD = 150000, B_SZ = 1, Q = 1, MAXN = 150010;
const int B_QTD = 1, B_SZ = 150000, Q = 1, MAXN = 150010;
int n, L, q_cnt;
int photo[MAXN], ult_coberto[MAXN], posicao[MAXN], myb[MAXN];
//photo[i] := comecando elephante i, #photo para terminar esse bucket
//ult_coberto[i]:= ultimo coordenada que meus photos cobri
//myb[i] := bucket que i pertence atualmente
set<pair<int, int>> eleph_in_order; //{posicao, id}
vector<int> buckets[B_QTD]; //id dos elephante ordenandas dividas nos buckets
int get_bucket(int i){
return i/B_SZ;
}
void make_bucket(vector<int> &v){
if(v.empty()) return;
//cerr << "nesse bucket contem: ";
// for(int id : v) //cerr << id << ' ';
//cerr << endl;
for(int l = v.size()-1, r = v.size(); l >= 0; l--){
while( posicao[ v[l] ] + L < posicao[ v[r-1] ]) r--;
//garanto que r eh primeuiro que n consigo cobrir
if(r == (int)v.size()){//caso eu cobro tudo mundo
dbln("*")
photo[ v[l] ] = 1;
ult_coberto[ v[l] ] = posicao[ v[l] ]+L;
db(v[l]) db(photo[v[l]]) db(posicao[v[l]]) dbln(ult_coberto[v[l]]);
}
else{
photo[ v[l] ] = 1+photo[ v[r] ];
ult_coberto[ v[l] ] = ult_coberto[ v[r] ];
db(v[l]) db(photo[v[l]]) dbln(ult_coberto[v[l]]);
}
}
}
//cada assign bucket deve ser feito em O(n)
void assign_buckets(){
for(int i = 0; i < B_QTD; i++) buckets[i].clear();
int i = 0;
for(auto it = eleph_in_order.begin(); it != eleph_in_order.end(); ++it, ++i){
int id = it->second;
myb[id] = get_bucket(i);
//cerr << "bucket " << myb[id] << " contem " << id << "\n";
buckets[myb[id]].push_back(id);
}
for(int i = B_QTD; i >= 0; i--) make_bucket(buckets[i]);
}
int find_answer(){
int ans = 0;
int i = 0, j = 0;
while(i < B_QTD && buckets[i].size()){
//bucket i, j-ésimo elefante vai começar foto
int no = buckets[i][j];
dbln(no);
ans += photo[no];
int uc = ult_coberto[no];
while( buckets[i+1].size() && i+1 < B_QTD && posicao[ buckets[i+1][0] ] <= uc ) i++;
//i := ultimo buckets que tem elephante incluido no foto
j = 0;
dbln(i);
for(int k = 11; k >= 0; k--){//cada buckets tem maximo 1250 elefantes
if(j + (1<<k) >= (int)buckets[i].size()) continue;
if( posicao[ buckets[i][j+(1<<k)] ] <= uc ) j += (1<<k);
dbln(j);
}
j++; //j:= quem eu n consigo pegar
if(j >= (int)buckets[i].size()){
j = 0;
i++;
}
dbln(j);
}
dbln(ans);
return ans;
}
void init(int N, int _L, int X[]){
n = N;
L = _L;
for(int i = 0; i < n; i++){
posicao[i] = X[i];
eleph_in_order.insert({X[i], i});
}
assign_buckets();
// int ans0 = find_answer();
// dbln(ans0);
}
//muda elephante i para posicao y
int update(int i, int y){
q_cnt++;
int pos0 = posicao[i];
posicao[i] = y;
eleph_in_order.erase({pos0, i});
eleph_in_order.insert({y, i});
if(q_cnt == Q){
assign_buckets();
q_cnt = 0;
}
else{
//recalcula bucket que me perdeu
vector<int> &antigo = buckets[ myb[i] ];
int id = 0;
while(id < (int)antigo.size() && antigo[id] != i) id++;
antigo.erase(antigo.begin()+id);
db(i) dbln(y);
dbln(myb[i]);
dbln("antigo")
// for(int a : antigo) //cerr << a << ' ';
//cerr << endl;
make_bucket(antigo);
//recalcula bucket que me ganhou
myb[i] = myb[eleph_in_order.upper_bound({y, i})->second];
vector<int> &novo = buckets[ myb[i] ];
id = 0;
while(id < (int)novo.size() && posicao[ novo[id] ] < y) id++;
novo.insert(novo.begin()+id, i);
dbln("novo")
// for(int a : novo) //cerr << a << ' ';
//cerr << endl;
make_bucket(novo);
}
return find_answer();
}
