#include "elephants.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int MAXN = 1e6 + 16;
const int MAX = 3e3 + 15;
int n, L, x[MAXN], block[MAXN], T, dp[MAX][MAX], d[MAX][MAX];
vector<int> blocks[MAX];
void init(int n_, int l_, int x_[]){
n = n_, L = l_;
T = sqrt(n) + 1;
for(int i = 0; i < n; i++)
x[i] = x_[i], blocks[i / T].push_back(x[i]);
}
void buildBlock(int b){
if(blocks[b].empty()) return;
int s = sz(blocks[b]);
for(int l = s - 1, r = s; l >= 0; l--){
int curX = blocks[b][l];
while(blocks[b][r - 1] - curX > L) r--;
if(r == s){
dp[b][l] = 1;
d[b][l] = curX + L;
}else{
dp[b][l] = dp[b][r] + 1;
d[b][l] = d[b][r];
}
}
}
void build(){
vector<int> aux;
for(int i = 0; i <= (n - 1) / T; i++){
for(auto& x : blocks[i]) aux.push_back(x);
blocks[i].clear();
}
for(int i = 0; i < n; i++)
blocks[i / T].push_back(aux[i]);
for(int i = 0; i <= (n - 1) / T; i++)
buildBlock(i);
}
int getBlock(int x){
for(int i = (n - 1) / T; i >= 0; i--)
if(blocks[i].size() && blocks[i][0] <= x) return i;
return 0;
}
int query(void){
int ans = 0;
for(int i = 0, r = -1; i <= (n - 1) / T; i++){
int idx = upper_bound(all(blocks[i]), r) - blocks[i].begin();
if(idx >= blocks[i].size()) continue;
ans += dp[i][idx];
r = d[i][idx];
}
return ans;
}
int update(int i, int y){
if(q++ % T == 0) build();
int b = getBlock(x[i]);
auto it = lower_bound(all(blocks[b]), x[i]);
blocks[b].erase(it);
buildBlock(b);
x[i] = y;
int nb = getBlock(y);
it = lower_bound(all(blocks[nb]), x[i]);
if(it == blocks[nb].end()) blocks[nb].push_back(x[i]);
else blocks[nb].insert(it, x[i]);
buildBlock(nb);
return query();
}
Compilation message
elephants.cpp: In function 'int query()':
elephants.cpp:69:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if(idx >= blocks[i].size()) continue;
| ~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:79:6: error: 'q' was not declared in this scope
79 | if(q++ % T == 0) build();
| ^
