#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
int n, l;
const int N = 150'005, B = 350;
struct block {
int n;
vector<int> v;
vector<array<int, 2>> dp;
void build() {
n = v.size();
dp.resize(n);
int p = n;
for (int i = n - 1; i >= 0; i--) {
while (p - 1 >= 0 && v[p - 1] >= v[i] + l) {
p--;
}
if (v[i] + l <= v.back()) {
dp[i] = {dp[p][0] + 1, dp[p][1]};
} else {
dp[i] = {1, v[i] + l};
}
}
}
void insert(int x) {
v.push_back(x);
for (int i = v.size() - 1; i - 1 >= 0; i--) {
if (v[i] <= v[i - 1]) {
swap(v[i], v[i - 1]);
} else {
break;
}
}
build();
}
void erase(int x) {
bool done = 0;
vector<int> newv;
for (int i = 0; i < SZ(v); i++) {
if (!done && v[i] == x) {
done = 1;
continue;
}
newv.push_back(v[i]);
}
v = newv;
build();
}
block(vector<int> &_v) {
v = _v;
n = v.size();
build();
}
};
vector<block> b;
void insert(int x) {
for (int i = 0; i < SZ(b); i++) {
if (i == SZ(b) - 1 || (b[i].v.back() <= x && x <= b[i + 1].v[0]) || (x <= b[i].v.back())) {
b[i].insert(x);
break;
}
}
}
void erase(int x) {
for (int i = 0; i < SZ(b); i++) {
if (b[i].v.empty()) continue;
if (b[i].v[0] <= x && x <= b[i].v.back()) {
b[i].erase(x);
break;
}
}
}
int query() {
int ans = 0, prv = 0;
for (int i = 0; i < SZ(b); i++) {
if (b[i].v.empty()) continue;
if (prv <= b[i].v.back()) {
int p = lower_bound(b[i].v.begin(), b[i].v.end(), prv) - b[i].v.begin();
ans += b[i].dp[p][0];
prv = b[i].dp[p][1];
}
}
return ans;
}
vector<int> a;
void build() {
vector<int> cur;
for (int i = 0; i < n; i++) {
if (cur.size() == B) {
b.push_back(cur);
cur.clear();
}
cur.push_back(a[i]);
}
b.push_back(cur);
}
void rebuild() {
a.clear();
for (int i = 0; i < SZ(b); i++) {
for (auto j : b[i].v) {
a.push_back(j);
}
}
b.clear();
build();
}
void init(int _n, int _l, int _a[]) {
n = _n, l = _l + 1;
a.resize(n);
for (int i = 0; i < n; i++) {
a[i] = _a[i];
}
build();
}
int cnt = 0;
int update(int x, int y) {
if (cnt == B) {
rebuild();
cnt = 0;
}
erase(a[x]);
a[x] = y;
insert(y);
return query();
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int _n, _l;
cin >> _n >> _l;
int _a[_n];
for (int i = 0; i < _n; i++) {
cin >> _a[i];
}
init(_n, _l, _a);
int _q;
cin >> _q;
while (_q--) {
int _i, _y;
cin >> _i >> _y;
cout << update(_i, _y) << '\n';
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccVjt2y5.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccTk67e7.o:elephants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
