#ifndef mikevui
// #include "task.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 15e4+5, B = 1000; ///B = 1000
int n, sumqu = 0, numblock, len, curpos[maxn];
vector<int> a; ///all positions
vector<vector<int>> b, cost, nxt; ///blocks
vector<int> temp; //for some use :V
void precal(vector<int> &b, vector<int> &cost, vector<int> &nxt) {
//init
int sz = b.size();
cost.assign(sz, 0);
nxt.assign(sz, 0);
int j = sz;
for (int i = sz-1; i >= 0; i--) {
while (j-1 > i && b[i]+len < b[j-1]) {
--j;
}
//init case
if (j == sz) {
cost[i] = 1;
nxt[i] = b[i] + len;
}
else {
cost[i] = cost[j] + 1;
nxt[i] = nxt[j];
}
}
// cout << "block:\n";
// for (int i = 0; i < sz; i++) {
// cout << b[i] << ' ';
// }
// cout << "\n";
// for (int i = 0; i < sz; i++) {
// cout << cost[i] << ' ';
// }
// cout << "\n";
// for (int i = 0; i < sz; i++) {
// cout << nxt[i] << ' ';
// }
// cout << "\n";
}
void extract() {
a.clear();
for (int j = 0; j < numblock; j++) {
for (int i = 0; i < (int)b[j].size(); i++) {
a.pb(b[j][i]);
}
}
}
void buildblocks() {
for (int i= 0; i < numblock; i++) {
b[i].clear();
}
for (int i = 0; i < n; i++) {
b[i/B].pb(a[i]);
}
//cal blocks
for (int i = 0; i < numblock; i++) {
precal(b[i], cost[i], nxt[i]);
}
}
void remval(int pos) {
int j = -1;
for (int k = numblock >> 1; k; k >>= 1) {
while (j+k < numblock-1 && b[j+k].back() < pos) j += k;
}
++j;
//this is the right block
bool found = 0;
for (int i = 0; i < (int)b[j].size(); i++) {
if (found || b[j][i] != pos) {
temp.pb(b[j][i]);
}
else {
found = 1;
}
}
swap(b[j], temp);
temp.clear();
// for (int i = 0; i < (int)b[j].size(); i++) {
// cout << b[j][i] << ' ';
// }
// cout << endl;
precal(b[j], cost[j], nxt[j]);
}
void insval(int pos) {
int j = -1;
for (int k = numblock >> 1; k; k >>= 1) {
while (j+k < numblock-1 && b[j+k].back() < pos) j += k;
}
++j;
// cout << j << endl;
// system("pause");
//this is the right block
bool found = 0;
for (int i = 0; i < (int)b[j].size(); i++) {
if (!found && pos < b[j][i]) {
found = 1;
temp.pb(pos);
}
temp.pb(b[j][i]);
}
if (!found) temp.pb(pos);
// system("pause");
swap(b[j], temp);
temp.clear();
// for (int i = 0; i < (int)b[j].size(); i++) {
// cout << b[j][i] << ' ';
// }
// cout << endl;
// system("pause");
precal(b[j], cost[j], nxt[j]);
}
int getans() {
int curnxt = -1, res = 0;
for (int j = 0; j < numblock; j++) {
//case nxt this block cover all of the next block
if (curnxt >= b[j].back()) continue;
//binsearch
int sz = b[j].size(), i = sz-1;
for (int k = sz>>1; k; k >>= 1){
while (i-k >= 0 && b[j][i-k] > curnxt) i -= k;
}
curnxt = nxt[j][i];
res += cost[j][i];
}
return res;
}
void init(int N, int L, vector<int> X) {
//normal
n = N;
len = L;
numblock = (n-1)/B+1;
b.assign(numblock, vector<int>());
cost.assign(numblock, vector<int>());
nxt.assign(numblock, vector<int>());
a = X;
for (int i = 0; i < n; i++) {
curpos[i] = a[i];
}
//build blocks
buildblocks();
}
int update(int id, int pos) {
//normal
++sumqu;
//remove
remval(curpos[id]);
// system("pause");
//insert
insval(pos);
curpos[id] = pos;
// cout << "ok" << endl;
// system("pause");
//answer -> binsearch
int ans = getans();
// system("pause");
//rebuild:
if (sumqu % (B-1) == 0) {
// cout << "entering rebuild" << endl;
// system("pause");
extract();
// system("pause");
buildblocks();
}
return ans;
}
#ifdef mikevui
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
int n, l;
vector<int> x;
cin >> n >> l;
for (int i = 0; i < n; i++) {
int v;
cin >> v;
x.pb(v);
}
init(n, l, x);
int q;
cin >> q;
while (q--) {
int id, pos;
cin >> id >> pos;
cout << update(id, pos) << "\n";
}
}
#endif // mikevui
/*
4 10
10 15 17 20
5
2 16
1 25
3 35
0 38
2 0
*/
Compilation message
/usr/bin/ld: /tmp/ccVPYB1n.o: in function `main':
grader.cpp:(.text.startup+0x27): undefined reference to `init(int, int, int*)'
collect2: error: ld returned 1 exit status
