#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll BIG = 1e9;
const ll ssz = 1<<3; // 1 << 20
const int INF = 1e9;
vector<int> seg_on(2*ssz, 0);
vector<int> seg_max(2*ssz, -INF), lz_max(2*ssz, 0);
void upd_on(int i, int x){
i += ssz;
seg_on[i] = x;
i /= 2;
while(i >= 1){
seg_on[i] = seg_on[2*i] + seg_on[2*i+1];
i /= 2;
}
}
int quer_on (int l, int r){
l += ssz;
r += ssz;
int res = 0;
while(l <= r){
if(l&1) res += seg_on[l++];
if(!(r&1)) res += seg_on[r--];
l /= 2;
r /= 2;
}
return res;
}
void pushdown(int rt, int tl, int tr){
seg_max[rt] += lz_max[rt];
if (tl != tr) {
lz_max[2*rt] += lz_max[rt];
lz_max[2*rt+1] += lz_max[rt];
}
lz_max[rt] = 0;
}
int query(int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (r < tl || l > tr) return -INF;
if (l <= tl && tr <= r) return seg_max[rt];
int mid = (tl + tr) / 2;
return max(query(l, r, 2*rt, tl, mid), query(l, r, 2*rt+1, mid+1, tr));
}
void update(int x, int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (r < tl || l > tr) return;
if (l <= tl && tr <= r) {
lz_max[rt] += x;
pushdown(rt, tl, tr);
return;
}
int mid = (tl + tr) / 2;
update(x, l, r, 2*rt, tl, mid);
update(x, l, r, 2*rt+1, mid+1, tr);
seg_max[rt] = max(seg_max[2*rt], seg_max[2*rt+1]);
}
void point_update(int x, int i){
update(x- query(i, i, 1, 0, ssz-1), i, i, 1, 0, ssz-1);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q=X.size();
int N = A.size();
vector<int> S(Q);
vector<ll> numvals(N), quervals(Q);
for(int i=0;i<N;++i) numvals[i] = A[i]*BIG + i;
for(int i=0;i<Q;++i) quervals[i] = V[i]*BIG + X[i];
set<ll> compress;
for(int i=0;i<N;++i) compress.insert(numvals[i]);
for(int i=0;i<Q;++i) compress.insert(quervals[i]);
map<ll, int> compress_map;
int idx = 0;
for(auto val : compress) {
compress_map[val] = idx++;
}
for(int i=0;i<N;++i) numvals[i] = compress_map[numvals[i]];
for(int i=0;i<Q;++i) quervals[i] = compress_map[quervals[i]];
for(int i=0;i<N;++i) upd_on(numvals[i], 1);
// output the full segment tree of segon
for(int i=0;i<N;++i){
point_update( i-(quer_on(0, numvals[i])-1), numvals[i]);
}
/*
for(int i=0;i<ssz;++i){
cout << query(i, i, 1, 0, ssz-1) << " ";
}
cout << endl;*/
// output each value of the segment tree
for(int i=0;i<Q;++i){
// newpos = X[i]
// turn off the old value
upd_on(numvals[X[i]],0);
point_update(-INF,numvals[X[i]]);
// update values between old and new
// old value = numvals[X[i]]
// new value = quervals[i]
// if it moves from small to big, add one to the elements
// else subtract one
if (numvals[X[i]] < quervals[i]){
update(1, numvals[X[i]], quervals[i], 1, 0, ssz-1);
}
else if (numvals[X[i]] > quervals[i]){
update(-1, quervals[i], numvals[X[i]], 1, 0, ssz-1);
}
// now update numvals
numvals[X[i]] = quervals[i];
upd_on(numvals[X[i]], 1);
point_update(X[i] - (quer_on(0, numvals[X[i]]) - 1), numvals[X[i]]);
// finally, query the value
S[i] = query(0, ssz-1, 1, 0, ssz-1);
}
return S;
}
