#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
constexpr int64_t N = 500000, L = 1ULL << 20;
int32_t T[2 * L][3];
void propagate(size_t k)
{
T[2 * k][0] += T[k][1];
T[2 * k][1] += T[k][1];
T[2 * k + 1][0] += T[k][1];
T[2 * k + 1][1] += T[k][1];
T[k][1] = 0;
}
void increment(size_t i, size_t j, int64_t x, size_t k = 1, size_t a = 0, size_t b = L)
{
if (b <= i || a >= j)
return;
if (i <= a && b <= j)
T[k][0] += x, T[k][1] += x;
else
{
propagate(k);
increment(i, j, x, 2 * k, a, (a + b) / 2);
increment(i, j, x, 2 * k + 1, (a + b) / 2, b);
T[k][0] = max(T[2 * k][0], T[2 * k + 1][0]);
T[k][2] = T[2 * k][2] + T[2 * k + 1][2];
}
}
void update(size_t i, int64_t x, size_t k = 1, size_t a = 0, size_t b = L)
{
if (b - a == 1)
{
T[k][0] = x;
T[k][2] = x != INT32_MIN / 2;
}
else
{
propagate(k);
if (i < (a + b) / 2)
update(i, x, 2 * k, a, (a + b) / 2);
else
update(i, x, 2 * k + 1, (a + b) / 2, b);
T[k][0] = max(T[2 * k][0], T[2 * k + 1][0]);
T[k][2] = T[2 * k][2] + T[2 * k + 1][2];
}
}
int64_t num_elements(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L)
{
if (b <= i || a >= j)
return 0;
if (i <= a && b <= j)
return T[k][2];
return num_elements(i, j, 2 * k, a, (a + b) / 2) +
num_elements(i, j, 2 * k + 1, (a + b) / 2, b);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
vector<size_t> coords;
for (size_t i = 0; i < A.size(); i++)
coords.push_back(A[i] * N + i);
for (size_t i = 0; i < X.size(); i++)
coords.push_back(V[i] * N + X[i]);
sort(coords.begin(), coords.end());
coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
for (size_t i = 0; i < A.size(); i++)
A[i] = lower_bound(coords.begin(), coords.end(), A[i] * N + i) - coords.begin();
for (size_t i = 0; i < X.size(); i++)
V[i] = lower_bound(coords.begin(), coords.end(), V[i] * N + X[i]) - coords.begin();
for (size_t i = L; i < 2 * L; i++)
T[i][0] = INT32_MIN / 2;
for (size_t i = 0; i < A.size(); i++)
T[L + A[i]][2] = 1;
for (size_t i = L - 1; i; i--)
T[i][2] = T[2 * i][2] + T[2 * i + 1][2];
for (size_t i = 0; i < A.size(); i++)
T[L + A[i]][0] = (int64_t)i - num_elements(0, A[i]);
for (size_t i = L - 1; i; i--)
T[i][0] = max(T[2 * i][0], T[2 * i + 1][0]);
vector<int> ans(X.size());
for (size_t i = 0; i < X.size(); i++)
{
update(A[X[i]], INT32_MIN / 2);
increment(A[X[i]], L, 1);
A[X[i]] = V[i];
increment(A[X[i]], L, -1);
update(A[X[i]], X[i] - num_elements(0, A[X[i]]));
ans[i] = T[1][0];
}
return ans;
}
int main()
{
size_t n, q;
cin >> n >> q;
vector<int> A(n), X(q), V(q);
for (int &x : A)
cin >> x;
for (int &x : X)
cin >> x;
for (int &x : V)
cin >> x;
auto ans = countScans(A, X, V);
for (int &x : ans)
cout << x << '\n';
}
Compilation message
/usr/bin/ld: /tmp/ccSXH7Bo.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4cyfJn.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
