#pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("Ofast") #include <bits/stdc++.h> #include "elephants.h" using namespace std; const int MAXN = 2e5 + 10; const int INF = 1e9; const int B = 100; const int UPD = 380; int x[MAXN], ind[MAXN]; pair<int, int> suf[MAXN]; set<pair<int, int>> s; vector<vector<pair<int, int>>> buckets; int n, l; int cnt_upd = 0; void process(int id){ auto &b = buckets[id]; if(b.empty()) return; int sz = (int) b.size(); suf[b[sz - 1].second] = {1, l}; int r = sz - 1; for(int i=(sz - 2); i>=0; i--){ while(b[r].first - b[i].first > l) r--; int last = 0; if(r < sz - 1) last = suf[b[r + 1].second].first; int extra = (b[i].first + l) - b[sz - 1].first; if(r < sz - 1) extra = suf[b[r + 1].second].second; suf[b[i].second] = {last + 1, extra}; } } void create_buckets(){ int cnt = 0; buckets.clear(); buckets.push_back({}); for(auto x : s){ if(cnt < B){ buckets.back().push_back(x); cnt ++; } else{ buckets.push_back({x}); cnt = 1; } ind[x.second] = (int) buckets.size() - 1; } for(int i=0; i<(int) buckets.size(); i++) process(i); } void refresh(){ cnt_upd ++; if(cnt_upd == UPD){ create_buckets(); cnt_upd = 0; } } int find_bucket(int x){ for(int i=0; i<(int) buckets.size(); i++){ if(!buckets[i].empty() && x <= buckets[i].back().first){ return i; } } return (int) buckets.size() - 1; } void remove(int id){ int j = ind[id]; vector<pair<int, int>> cur; for(auto x : buckets[j]){ if(x.second == id) continue; cur.push_back(x); } s.erase({x[id], id}); buckets[j] = cur; process(j); } void add(int id){ int j = find_bucket(x[id]); ind[id] = j; vector<pair<int, int>> cur; int sz = (int) buckets[j].size(); if(sz > 0){ if(x[id] < buckets[j][0].first) cur.push_back({x[id], id}); for(int i=0; i<(sz - 1); i++){ cur.push_back(buckets[j][i]); if(buckets[j][i].first <= x[id] && x[id] < buckets[j][i + 1].first){ cur.push_back({x[id], id}); } } cur.push_back(buckets[j][sz - 1]); if(buckets[j][sz - 1].first <= x[id]) cur.push_back({x[id], id}); } else cur = {{x[id], id}}; buckets[j] = cur; s.insert({x[id], id}); process(j); } int query(){ int ans = 0; int cur = 0; for(int i=0; i<(int) buckets.size(); i++){ if(!buckets[i].empty()){ cur = buckets[i][0].second; break; } } while(true){ ans += suf[cur].first; int nxt = buckets[ind[cur]].back().first + suf[cur].second; auto pos = s.upper_bound({nxt, INF}); if(pos == s.end()) break; cur = pos->second; } return ans; } void init(int n_, int l_, int x_[]){ n = n_; l = l_; cnt_upd = 0; for(int i=0; i<n; i++) x[i] = x_[i]; s.clear(); for(int i=0; i<n; i++) s.insert({x[i], i}); create_buckets(); } int update(int id, int y){ remove(id); x[id] = y; add(id); refresh(); return query(); }