#include "bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int,int> merge(const pair<int,int>& p1, const pair<int,int>& p2)
{
return make_pair(max(p1.first, p2.first), p1.second + p2.second);
}
struct segtree
{
vector<pair<int,int>> table;
vector<int> op;
void apply(int pos, int o)
{
table[pos].first += o;
op[pos] += o;
}
void propagate(int pos)
{
apply(2*pos + 1, op[pos]);
apply(2*pos + 2, op[pos]);
op[pos] = 0;
}
pair<int,int> query(int ql, int qr, int l, int r, int pos)
{
if (ql <= l && r <= qr) return table[pos];
if (r < ql || qr < l) return {-1e8, 0};
propagate(pos);
return merge(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
}
void update(int ql, int qr, int o, int l, int r, int pos)
{
if (ql <= l && r <= qr) { apply(pos, o); return; }
if (r < ql || qr < l) return;
propagate(pos);
update(ql, qr, o, l, (l + r)/2, 2*pos + 1);
update(ql, qr, o, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
}
void set(int k, int v, int l, int r, int pos)
{
if (l == r)
{
table[pos].first = v;
table[pos].second = (v > -1e7);
return;
}
propagate(pos);
if (k <= (l + r)/2) set(k, v, l, (l + r)/2, 2*pos + 1);
else set(k, v, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
int n = a.size();
int q = x.size();
vector<pair<int,int>> comp;
for (int i = 0; i < n; i++) comp.emplace_back(a[i], i);
for (int i = 0; i < q; i++) comp.emplace_back(v[i], x[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for (int i = 0; i < n; i++) a[i] = lower_bound(comp.begin(), comp.end(), make_pair(a[i], i)) - comp.begin();
for (int i = 0; i < q; i++) v[i] = lower_bound(comp.begin(), comp.end(), make_pair(v[i], x[i])) - comp.begin();
int vs = comp.size();
segtree st;
st.op.resize(4*vs);
st.table.resize(4*vs, {-1e8, 0});
auto insert = [&](int pos, int ind)
{
int lf = st.query(0, ind - 1, 0, vs - 1, 0).second;
st.update(ind + 1, vs - 1, -1, 0, vs - 1, 0);
st.set(ind, pos - lf, 0, vs - 1, 0);
};
auto remove = [&](int ind)
{
st.update(ind + 1, vs - 1, 1, 0, vs - 1, 0);
st.set(ind, -1e8, 0, vs - 1, 0);
};
for (int i = 0; i < n; i++)
{
insert(i, a[i]);
}
vector<int> res;
for (int i = 0; i < q; i++)
{
remove(a[x[i]]);
insert(x[i], v[i]);
a[x[i]] = v[i];
res.push_back(st.query(0, vs - 1, 0, vs - 1, 0).first);
}
return res;
}
