#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
struct node {
node *left, *right;
ii key;
int val, mx, sz;
int prior, lazy;
node(ii k, int v) {
left = right = NULL;
key = k;
val = mx = v;
sz = 1;
prior = rand();
lazy = 0;
}
};
typedef node* pnode;
void push(pnode t) {
if (!t || t->lazy == 0)
return;
t->val += t->lazy;
t->mx += t->lazy;
if (t->left)
t->left->lazy += t->lazy;
if (t->right)
t->right->lazy += t->lazy;
t->lazy = 0;
}
void update(pnode t) {
if (!t) return;
push(t->left);
push(t->right);
t->mx = t->val;
t->sz = 1;
if (t->left) {
t->mx = max(t->mx, t->left->mx);
t->sz += t->left->sz;
}
if (t->right) {
t->mx = max(t->mx, t->right->mx);
t->sz += t->right->sz;
}
}
void split(pnode t, pnode &L, pnode &R, ii k) {
if (!t) {
L = R = NULL;
return;
}
push(t);
if (k < t->key) {
split(t->left, L, t->left, k);
R = t;
} else {
split(t->right, t->right, R, k);
L = t;
}
update(t);
}
void merge(pnode &t, pnode L, pnode R) {
push(L); push(R);
if (!L || !R) {
t = (L ? L : R);
return;
}
if (L->prior > R->prior) {
merge(L->right, L->right, R);
t = L;
} else {
merge(R->left, L, R->left);
t = R;
}
update(t);
}
void inorder(pnode t) {
if (!t) return;
push(t);
update(t);
inorder(t->left);
printf("(%d, %d): val = %d, mx = %d\n", t->key.fi, t->key.se, t->val, t->mx);
inorder(t->right);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
srand(time(NULL));
vector<ii> sor;
int n = (int)A.size();
for (int i = 0; i < n; i++) {
sor.pb(mp(A[i], i));
}
sort(sor.begin(), sor.end());
pnode root = NULL;
for (int i = 0; i < n; i++) {
merge(root, root, new node(sor[i], sor[i].se - i));
}
vector<int> ans;
int q = (int)X.size();
for (int i = 0; i < q; i++) {
ii bef = mp(A[X[i]], X[i]);
A[X[i]] = V[i];
ii aft = mp(A[X[i]], X[i]);
pnode other = NULL, dummy = NULL;
split(root, root, other, bef);
if (other) {
other->lazy++;
push(other);
}
split(root, root, dummy, mp(bef.fi, bef.se - 1));
delete dummy;
merge(root, root, other);
split(root, root, other, aft);
merge(root, root, new node(aft, X[i] - (root ? root->sz : 0)));
if (other) {
other->lazy--;
push(other);
}
merge(root, root, other);
//puts("NOW INORDER");inorder(root);
ans.pb(root->mx);
}
return ans;
}
