#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define fi first #define sc second const int MAXN = 150005; int suf[MAXN], x[MAXN], extra[MAXN], marc[MAXN], n, tam = 1250, l, cur; set<pair<int,int>> st; vector< vector< pair<int,int> > > buckets; void fazbucket(int i){ int lst = buckets[i].size()-1; for(int j = buckets[i].size()-1; j >= 0; j--){ while(buckets[i][lst].fi - buckets[i][j].fi > l)lst--; if(lst+1 < buckets[i].size()){ suf[ buckets[i][j].sc ] = suf[ buckets[i][lst+1].sc ] + 1; extra[ buckets[i][j].sc ] = extra[ buckets[i][lst+1].sc ]; }else{ suf[ buckets[i][j].sc ] = 1; extra[ buckets[i][j].sc ] = buckets[i][j].fi + l; } } } void faz(){ auto it = st.rbegin(); buckets.clear(); int qtd = 0, b = 0; buckets.push_back({}); while(it != st.rend()){ if(qtd == tam){ reverse(buckets[b].begin(),buckets[b].end()); fazbucket(b); buckets.push_back({}); qtd = 0; b++; } qtd++; marc[it->sc] = b; buckets[b].push_back(*it); it++; } reverse(buckets[b].begin(),buckets[b].end()); fazbucket(b); } void init(int N, int L, int X[]) { n = N; l = L; for(int i = 0; i < n; i++){ st.insert({X[i],i}); x[i] = X[i]; } faz(); } int update(int i, int y) { cur++; if(cur == 387){ st.erase({x[i],i}); x[i] = y; st.insert({x[i],i}); cur = 0; faz(); }else{ st.erase({x[i],i}); for(int j = 0; j < buckets[ marc[i] ].size(); j++) if(buckets[ marc[i] ][j].sc == i){ buckets[ marc[i] ].erase(buckets[marc[i]].begin()+j); break; } fazbucket(marc[i]); x[i] = y; st.insert({x[i],i}); marc[i] = buckets.size()-1; for(int j = 0; j < buckets.size(); j++) if(buckets[j][0].fi <= x[i]){ marc[i] = j; break; } for(int j = buckets[ marc[i] ].size()-1; j >= -1; j--) if(j == -1 || buckets[ marc[i] ][j].fi < x[i]){ buckets[ marc[i] ].insert(buckets[marc[i]].begin()+j+1, {x[i],i} ); break; } fazbucket(marc[i]); } int ii = st.begin()->sc, ans = 0; while(1){ ans += suf[ii]; auto it = st.upper_bound({extra[ii], 100000000}); if(it == st.end())break; ii = it->sc; } return ans; }