#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i += (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9;
struct node{
int lazy = 0;
int max = 0;
void apply(int l, int r, int val){
lazy += val;
max += val;
}
};
struct segtree{
node comb(const node& a, const node &b){
node res;
res.max = max(a.max, b.max);
return res;
}
void push(int l, int r, int v){
tree[v << 1].apply(l, r, tree[v].lazy);
tree[v << 1 | 1].apply(l, r, tree[v].lazy);
tree[v].lazy = 0;
}
int n;
vector<node> tree;
segtree(int _n){
n = 1;
while(n < _n)
n *= 2;
tree.resize(2 * n);
}
node query(int l, int r){
return query0(l, r, 0, n, 1);
}
node query0(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r)
return tree[v];
if(beg >= r || end <= l){
node res;
res.max = -INF;
return res;
}
push(beg, end, v);
int mid = (beg + end) >> 1;
return comb(query0(l, r, beg, mid, v << 1), query0(l, r, mid, end, v << 1 | 1));
}
void upd(int l, int r, int val){
upd0(l, r, 0, n, 1, val);
}
void upd0(int l, int r, int beg, int end, int v, int val){
if(beg >= l && end <= r){
tree[v].apply(beg, end, val);
return;
}
if(beg >= r || end <= l)
return;
push(beg, end, v);
int mid = (beg + end) >> 1;
upd0(l, r, beg, mid, v << 1, val);
upd0(l, r, mid, end, v << 1 | 1, val);
tree[v] = comb(tree[v << 1], tree[v << 1 | 1]);
}
};
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
int q = x.size();
int n = a.size();
vector<int> res(q);
vector<array<int, 3>> comp;
REP(i, n){
comp.pb({a[i], i, -1});
}
REP(i, q){
comp.pb({v[i], x[i], i});
}
sort(comp.begin(), comp.end());
// values compressed; if they were equal initially, they are tiebreaked using index; if index > .., compression value is bigger
REP(i, comp.size()){
auto y = comp[i];
if(y[2] == -1){ // in intiail array
a[y[1]] = i;
}
else{
v[y[2]] = i;
}
}
segtree st(comp.size() + 10);
st.upd(0, st.n, -INF);
REP(i, n){
st.upd(a[i], a[i] + 1, INF + i);
st.upd(a[i] + 1, st.n, -1);
}
REP(i, q){
int id = x[i];
st.upd(a[id], a[id] + 1, -INF - id);
st.upd(a[id] + 1, st.n, 1);
a[id] = v[i];
st.upd(a[id], a[id] + 1, INF + id);
st.upd(a[id] + 1, st.n, -1);
auto no = st.query(0, st.n);
res[i] = no.max;
}
return res;
}
