#include "bubblesort2.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct FenwickTree {
vector<int> tree;
int size;
FenwickTree(int n) {
size = n;
tree.resize(size);
}
void update(int pos, int value) {
for (int i = pos; i < size; i |= i + 1) {
tree[i] += value;
}
}
int query(int l, int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
res += tree[i];
}
for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
res -= tree[i];
}
return res;
}
};
const int INF = 1e9;
struct SegmentTree {
struct Node {
int value;
int push;
Node(int _value = -INF, int _push = 0)
: value(_value), push(_push) {}
friend Node combine(const Node& lhs, const Node& rhs) {
return {max(lhs.value, rhs.value), 0};
}
};
vector<Node> tree;
int size;
SegmentTree(int n) {
size = 1 << (__lg(n) + 1);
tree.resize(2 * size - 1);
}
void point_update(int pos, int value) {
point_update(0, size, 0, pos, value);
}
void point_update(int l, int r, int v, int pos, int value) {
push(l, r, v);
if (l == r - 1) {
tree[v].value = value;
return;
}
int m = (l + r) / 2;
if (pos < m) {
point_update(l, m, 2 * v + 1, pos, value);
} else {
point_update(m, r, 2 * v + 2, pos, value);
}
tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
}
void update(int lq, int rq, int value) {
update(0, size, 0, lq, rq, value);
}
void apply(int v, int value) {
tree[v].value += value;
tree[v].push += value;
}
void push(int l, int r, int v) {
if (l == r - 1 || tree[v].push == 0) return;
apply(2 * v + 1, tree[v].push);
apply(2 * v + 2, tree[v].push);
tree[v].push = 0;
}
void update(int l, int r, int v, int lq, int rq, int value) {
push(l, r, v);
if (lq <= l && r <= rq) {
apply(v, value);
return;
} else if (l >= rq || r <= lq) {
return;
}
int m = (l + r) / 2;
update(l, m, 2 * v + 1, lq, rq, value);
update(m, r, 2 * v + 2, lq, rq, value);
tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
}
int get_max() const {
return tree[0].value;
}
};
vector<int> countScans(vector<int> a, vector<int> pos, vector<int> value){
int n = a.size();
int q = pos.size();
vector<int> all_values = a;
all_values.insert(all_values.end(), value.begin(), value.end());
sort(all_values.begin(), all_values.end());
all_values.resize(unique(all_values.begin(), all_values.end()) - all_values.begin());
int k = all_values.size();
map<int, int> mp;
for (int i = 0; i < k; ++i) {
mp[all_values[i]] = i;
}
for (auto& x : a) {
x = mp[x];
}
for (auto& x : value) {
x = mp[x];
}
FenwickTree tree(k);
for (auto x : a) {
tree.update(x, 1);
}
SegmentTree segtree(k);
vector<set<int, greater<int>>> occurs(k);
for (int i = 0; i < n; ++i) {
segtree.point_update(a[i], i - tree.query(0, a[i]) + 1);
occurs[a[i]].insert(i);
}
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
{
int x = a[pos[i]];
tree.update(x, -1);
occurs[x].erase(pos[i]);
segtree.update(x, k, 1);
if (occurs[x].empty()) {
segtree.point_update(x, -INF);
} else {
int new_value = *occurs[x].begin() - tree.query(0, x) + 1;
segtree.point_update(x, new_value);
}
}
{
int x = value[i];
a[pos[i]] = x;
occurs[x].insert(pos[i]);
tree.update(x, 1);
int new_value = *occurs[x].begin() - tree.query(0, x) + 1;
segtree.update(x, k, -1);
segtree.point_update(x, new_value);
}
ans[i] = segtree.get_max();
}
return ans;
}
