#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct Tag {
int add;
Tag(int _add) : add(_add) {}
Tag() : add(0) {}
void apply(Tag &tag) { add += tag.add; }
};
struct Info {
int hi;
Info(int _hi) : hi(_hi) {}
Info() : hi(0) {}
void apply(Tag &tag) { hi += tag.add; }
Info combine(Info &other) { return {max(hi, other.hi)}; }
};
struct Tree {
vector<Tag> tag;
vector<Info> info;
Tree(int size) {
tag.resize(size*4);
info.resize(size*4);
}
void build(vector<Info> &base, int x, int xl, int xr) {
if (xl == xr) {
info[x] = base[xl];
} else {
int xm = (xl + xr) / 2;
build(base, x*2, xl, xm);
build(base, x*2+1, xm+1, xr);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
void pushdown(int x) {
info[x].apply(tag[x]);
if (x*2 < (int) tag.size()) tag[x*2].apply(tag[x]);
if (x*2+1 < (int) tag.size()) tag[x*2+1].apply(tag[x]);
tag[x] = {};
}
void update(int l, int r, int x, int xl, int xr, Tag delta) {
if (l > r) return;
pushdown(x);
if (l == xl && r == xr) {
tag[x].apply(delta);
} else {
int xm = (xl + xr) / 2;
update(l, min(r, xm), x*2, xl, xm, delta);
update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
pushdown(x); pushdown(x*2); pushdown(x*2+1);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
Info query(int l, int r, int x, int xl, int xr) {
if (l > r) return {};
pushdown(x);
if (l == xl && r == xr) {
return info[x];
} else {
int xm = (xl + xr) / 2;
Info left = query(l, min(r, xm), x*2, xl, xm);
Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
return left.combine(right);
}
}
};
// need to only query from a number if it is smaller than everything
// to the right of it
// i.e. pick the rightmost item, then the next smallest and next and so on
// if it is smaller than everything to the right, then i can
// count the number of items above it and subtract it from how much stuff is
// on the right, to get it ans
// in other words, this can be done if we use a segment tree to count number below x
// we can update one of these important values
// now we just need to be able to identify and track how these values change
// for now let's just see if i can get 60 points
// ok for 100 points it shouldnt be too tricky
// i need max segment tree of the following statistic:
// - amount of numbers above this value minus this index
// - but we can do a segment tree on the values themselves
// - sgt[v] = (number of values > v) - N + 1 + highest 'j'
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int N = A.size();
int Q = X.size();
set<int> AV;
for (int a : A) AV.insert(a);
for (int v : V) AV.insert(v);
map<int,int> idxmap; int T = 0;
for (int av : AV) idxmap[av] = T++;
Tree tree(T);
vector<set<int>> idx(T);
for (int i=0; i<N; i++) {
A[i] = idxmap[A[i]];
idx[A[i]].insert(i);
if (A[i] > 0) tree.update(0, A[i]-1, 1, 0, T-1, {+1});
}
auto updJ = [&](int i, int mul) -> void {
int j = idx[i].empty() ? -1'000'000 : *idx[i].rbegin();
tree.update(i, i, 1, 0, T-1, {mul * j});
};
for (int i=0; i<T; i++) {
updJ(i, +1);
}
vector<int> ans(Q);
for (int i=0; i<Q; i++) {
updJ(A[X[i]], -1);
idx[A[X[i]]].erase(X[i]);
updJ(A[X[i]], +1);
if (A[X[i]] > 0) tree.update(0, A[X[i]]-1, 1, 0, T-1, {-1});
A[X[i]] = idxmap[V[i]];
if (A[X[i]] > 0) tree.update(0, A[X[i]]-1, 1, 0, T-1, {+1});
updJ(A[X[i]], -1);
idx[A[X[i]]].insert(X[i]);
updJ(A[X[i]], +1);
ans[i] = tree.query(0, T-1, 1, 0, T-1).hi - N + 1;
}
return ans;
}
