#include "elephants.h" #include<bits/stdc++.h> using namespace std; const int B_QTD = 120, B_SZ = 1255, Q = 400, MAXN = 150010; int n, L, q_cnt; int photo[MAXN], ult_coberto[MAXN], posicao[MAXN], myb[MAXN]; 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; for(int l = v.size()-1, r = v.size(); l >= 0; l--){ while( posicao[ v[l] ] + L < posicao[ v[r-1] ]) r--; if(r == (int)v.size()){//caso eu cobro tudo mundo photo[ v[l] ] = 1; ult_coberto[ v[l] ] = posicao[ v[l] ]+L; } else{ photo[ v[l] ] = 1+photo[ v[r] ]; ult_coberto[ v[l] ] = ult_coberto[ v[r] ]; } } } 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); 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){ if(buckets[i].empty()){ i++; continue; } int no = buckets[i][j]; ans += photo[no]; int uc = ult_coberto[no]; int li = 0; for(; i < B_QTD; i++){ if(buckets[i].empty()) continue; if(posicao[ buckets[i][0] ] <= uc) li = i; if(posicao[ buckets[i].back() ] > uc) break; } j = 0; for(int k = 11; k >= 0; k--){//cada buckets tem maximo 1250 elefantes if(j + (1<<k) >= (int)buckets[li].size()) continue; if( posicao[ buckets[li][j+(1<<k)] ] <= uc ) j += (1<<k); } j++; //j:= quem eu n consigo pegar if(j >= (int)buckets[li].size()){ j = 0; i = li+1; } } 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 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{ vector<int> &antigo = buckets[ myb[i] ]; int id = 0; while(id < (int)antigo.size() && antigo[id] != i) id++; antigo.erase(antigo.begin()+id); make_bucket(antigo); auto frente_de_mim = eleph_in_order.upper_bound({y, i}); if(frente_de_mim == eleph_in_order.end()) --frente_de_mim, --frente_de_mim; myb[i] = myb[frente_de_mim->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); make_bucket(novo); } return find_answer(); }