#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
// Number of scans = max_i{#elements greater than A[i] on the left of i}
// #elements greater than A[i] on the left of A[i] = i - #elements less
// or equal to A[i] on the left of A[i].
//
// If there is i < j and A[i] > A[j], then we will never consider i as
// a maximum candidate. Thus we can actually only find the maximum value
// of i - #elements less or equal to than A[i], since we only consider an i such
// that there is no elements lesser than A[i] on its right.
//
// We can keep a segment tree storing values (i - #elements less or equal to A[i]).
// We can do a range update and range maximum query to find the answer.
//
// Time: O((N + Q) log N)
const int INF = 1e7;
class SegTree {
public:
int sz;
vector<int> tree;
vector<int> lazy;
SegTree() {}
SegTree(int sz) : sz(sz), tree(2 * sz, -INF), lazy(2 * sz) {}
void Apply(int n, int x) {
tree[n] += x;
lazy[n] += x;
}
void Push(int n, int lc, int rc) {
Apply(lc, lazy[n]);
Apply(rc, lazy[n]);
lazy[n] = 0;
}
void Pull(int n, int lc, int rc) {
tree[n] = max(tree[lc], tree[rc]);
}
void RangeAdd(int n, int tl, int tr, int l, int r, int x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) return Apply(n, x);
int md = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (md - tl + 1);
Push(n, lc, rc);
RangeAdd(lc, tl, md, l, r, x);
RangeAdd(rc, md + 1, tr, l, r, x);
Pull(n, lc, rc);
}
void RangeAdd(int l, int r, int x) {
return RangeAdd(1, 0, sz - 1, l, r, x);
}
void Modify(int n, int tl, int tr, int p, int x) {
if (tl == tr) return void(tree[n] = x);
int md = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (md - tl + 1);
Push(n, lc, rc);
if (p <= md) {
Modify(lc, tl, md, p, x);
} else {
Modify(rc, md + 1, tr, p, x);
}
Pull(n, lc, rc);
}
void Modify(int p, int x) {
return Modify(1, 0, sz - 1, p, x);
}
int Query() {
return tree[1];
}
};
class Fenwick {
public:
int sz;
vector<int> tree;
Fenwick() {}
Fenwick(int sz) : sz(sz), tree(sz) {}
void Update(int p, int x) {
for (int i = p; i < sz; i |= i + 1) {
tree[i] += x;
}
}
int Query(int p) {
int res = 0;
for (int i = p; i > 0; i &= i - 1) {
res += tree[i - 1];
}
return res;
}
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int N = A.size();
int Q = X.size();
vector<pair<int, int>> coords;
for (int i = 0; i < N; i++) {
coords.emplace_back(A[i], i);
}
for (int i = 0; i < Q; i++) {
coords.emplace_back(V[i], X[i]);
}
sort(begin(coords), end(coords));
coords.resize(unique(begin(coords), end(coords)) - begin(coords));
auto Position = [&](int x, int y) -> int {
return lower_bound(begin(coords), end(coords), make_pair(x, y)) - begin(coords);
};
SegTree seg(coords.size());
Fenwick active(coords.size());
for (int i = 0; i < N; i++) {
active.Update(Position(A[i], i), 1);
}
for (int i = 0; i < N; i++) {
seg.Modify(Position(A[i], i), i - active.Query(Position(A[i], i)));
}
vector<int> answer(Q);
for (int i = 0; i < Q; i++) {
seg.RangeAdd(Position(A[X[i]], X[i]) + 1, int(coords.size()) - 1, +1);
seg.Modify(Position(A[X[i]], X[i]), -INF);
active.Update(Position(A[X[i]], X[i]), -1);
A[X[i]] = V[i];
active.Update(Position(A[X[i]], X[i]), +1);
seg.RangeAdd(Position(A[X[i]], X[i]) + 1, int(coords.size()) - 1, -1);
seg.Modify(Position(A[X[i]], X[i]), X[i] - active.Query(Position(A[X[i]], X[i])));
answer[i] = seg.Query();
}
return answer;
}
