#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using OSet = tree <T, null_type, std::less <T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long llong;
const int MAXN = 500000 + 10;
const int MAXNUM = 1e6 + 10;
const int INF = 1e9;
int n, q;
int cntDiff;
struct SegmentTree
{
struct Node
{
int max;
int val;
int lazy;
bool isActive;
Node()
{
max = lazy = isActive = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
res.max = std::max(left.max, right.max);
res.isActive = left.isActive | right.isActive;
return res;
}
};
Node tree[4*MAXNUM];
void push(int node, int l, int r)
{
if (tree[node].lazy == 0)
{
return;
}
if (tree[node].isActive)
{
tree[node].max += tree[node].lazy;
}
if (l == r)
{
tree[node].val += tree[node].lazy;
} else
{
tree[2*node].lazy += tree[node].lazy;
tree[2*node + 1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
void updateActive(int l, int r, int node, int queryPos, int queryIdx)
{
push(node, l, r);
if (queryPos < l || r < queryPos)
{
return;
}
if (l == r)
{
if (tree[node].isActive)
{
tree[node].isActive = 0;
tree[node].max = 0;
} else
{
tree[node].isActive = true;
tree[node].max = queryIdx - 1 + tree[node].val;
}
return;
}
int mid = (l + r) / 2;
updateActive(l, mid, 2*node, queryPos, queryIdx);
updateActive(mid + 1, r, 2*node + 1, queryPos, queryIdx);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void updateRange(int l, int r, int node, int queryL, int queryR, int queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy += queryVal;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
updateRange(l, mid, 2*node, queryL, queryR, queryVal);
updateRange(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
int query()
{
return tree[1].max;
}
void add(int idx, int val)
{
updateActive(1, cntDiff, 1, val, idx);
if (val < cntDiff) updateRange(1, cntDiff, 1, val + 1, cntDiff, -1);
}
void remove(int idx, int val)
{
updateActive(1, cntDiff, 1, val, idx);
if (val < cntDiff) updateRange(1, cntDiff, 1, val + 1, cntDiff, 1);
}
};
int in[MAXN];
int pos[MAXN];
int order[MAXN];
int updatePos[MAXN];
llong updateVal[MAXN];
SegmentTree tree;
llong a[MAXN];
std::vector <int> countScans(std::vector <int> A, std::vector <int> X, std::vector <int> V)
{
n = A.size();
q = X.size();
std::vector <std::pair <llong, std::pair <int,bool>>> v;
for (int i = 1 ; i <= n ; ++i)
{
a[i] = 1LL * n * A[i - 1] + i;
v.push_back({a[i], {i, true}});
}
for (int i = 0 ; i < q ; ++i)
{
updatePos[i + 1] = X[i] + 1;
updateVal[i + 1] = 1LL * n * V[i] + updatePos[i + 1];
v.push_back({updateVal[i + 1], {i + 1, false}});
}
std::sort(v.begin(), v.end());
for (int i = 0 ; i < v.size() ; ++i)
{
cntDiff += (i == 0 || v[i].first > v[i - 1].first);
if (v[i].second.second) a[v[i].second.first] = cntDiff;
else updateVal[v[i].second.first] = cntDiff;
}
for (int i = 1 ; i <= n ; ++i)
{
tree.add(i, a[i]);
}
std::vector <int> answer(q, 0);
for (int i = 1 ; i <= q ; ++i)
{
tree.remove(updatePos[i], a[updatePos[i]]);
a[updatePos[i]] = updateVal[i];
tree.add(updatePos[i], a[updatePos[i]]);
answer[i - 1] = tree.query();
}
return answer;
}
