#include "elephants.h" #include<bits/stdc++.h> using namespace std; const int maxn=150010; const int sqtb=121; // qtd de buckets const int sqtt=2; // qtd de caras no buckets const int sqtq=2; // qtd de queries q precisa ter pra dar reset const int inf=1e9+7; int n, qtd_upd, l; multiset<int>ms; vector<pair<int,int>>buckets; // guardando o ini e fim dos buckets vector<vector<int>>caras; pair<int,int> dp[sqtb][sqtt+10]; // dp[bucket][cara] = {cost,sobra} int v[maxn]; void init(int N, int L, int X[]){ n=N; l=L; for(int i=0;i<N;i++){ v[i]=X[i]; ms.insert(X[i]); } } void colocar(int i, int x){ vector<int>aux; while(caras[i].size()&&x<=caras[i].back()){ aux.push_back(caras[i].back()); caras[i].pop_back(); } caras[i].push_back(x); // colocando o x novo while(aux.size()){ caras[i].push_back(aux.back()); aux.pop_back(); } } void tirar(int i, int x){ vector<int>aux; while(caras[i].size()&&x<=caras[i].back()){ aux.push_back(caras[i].back()); caras[i].pop_back(); } aux.pop_back(); // tirando um dos x while(aux.size()){ caras[i].push_back(aux.back()); aux.pop_back(); } } void recalc(int i){ // recalculo a dp do bucket i for(int j=0;j<caras[i].size();j++) dp[i][j]={inf,0}; for(int j=caras[i].size()-1;j>=0;j--){ int at=caras[i][j]; int sobra=l-(buckets[i].second-at), cost=1; if(caras[i].back()>at+l){ // vendo se eu cubro o ultimo cara int id=upper_bound(caras[i].begin(),caras[i].end(),at+l)-caras[i].begin(); // pegando o id do primeiro cara q n cubro do bucket cost=dp[i][id].first+1; sobra=dp[i][id].second; } if(dp[i][j].first>cost) dp[i][j]={cost,sobra}; else if(dp[i][j].first==cost&&dp[i][j].second<sobra) dp[i][j]={cost,sobra}; } cerr << "dp of " << i << ": " << endl; for(int j=0;j<caras[i].size();j++) cerr << dp[i][j].first << " " << dp[i][j].second << endl; cerr << endl; } int simular(){ // cout << "! enter " << buckets.size() << endl; int id=-1, resp=0; for(int i=0;i<buckets.size();i++){ cerr << buckets[i].first << " " << buckets[i].second << endl; if(caras[i].empty()) continue; // n tem ninguem pra cobrir if(caras[i].back()<=id) continue; // n preciso aumentar a resposta, ja q o outro intervalo cobre tudo int at=upper_bound(caras[i].begin(),caras[i].end(),id)-caras[i].begin(); // pegando o id da proxima dp cerr << "! " << at << " " << dp[i][at].first << " " << at+l << endl; resp+=dp[i][at].first; id=buckets[i].second+dp[i][at].second; // ate onde eu cubro } cerr << endl; return resp; } int update(int i, int y){ // att o multiset, para qnd precisar dar recalc em tds int ant=v[i]; ms.erase(ms.find(v[i])); v[i]=y; ms.insert(v[i]); if((qtd_upd%sqtq)==0){ // reconstruir os buckets cerr << "recalc all" << endl; buckets.clear(); caras.clear(); int cnt=0, ini=-1, last=-1; // for(int x : ms) cout << x << ' '; // cout << endl; vector<int>aux; for(int x : ms){ // cerr << cnt << " " << x << endl; cnt++; aux.push_back(x); if(cnt==sqtt){ buckets.push_back({ini,x}); caras.push_back(aux); aux.clear(); ini=x; } cnt%=sqtt; } cerr << "orz" << endl; if(cnt){ buckets.push_back({ini,inf}); caras.push_back(aux); }else buckets.back().second=inf; for(int i=0;i<buckets.size();i++) recalc(i); }else{ cerr << "substituting: " << ant << " " << y << endl; bool ok1=false, ok2=false; for(int i=0;i<buckets.size();i++){ if(buckets[i].first<=y&&y<=buckets[i].second&&ok1==false){ cerr << "a" << endl; ok1=true; colocar(i,y); cerr << "recalc only " << i << ": " << endl; recalc(i); } if(caras[i].size()&&caras[i][0]<=ant&&ant<=caras[i].back()&&ok2==false){ cerr << "b" << endl; ok2=true; tirar(i,ant); cerr << "recalc only " << i << ": " << endl; recalc(i); } } assert(ok1&&ok2); cerr << endl; } qtd_upd++; return simular(); }