#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define dec nice_macro
#define maxn 1000010
int N, Q;
int seg[maxn*4];
int delt[maxn*4];
multiset<int> leaves[maxn]; //(think we want this stuff)
map<int, int> dec;
int ovals[maxn]; //number less than or equal to each value in initial sequence
int cvals[maxn];
int query() {
//just return the top of the segment tree plus the deltas
return seg[0];
}
void av(int ai, int val, int ss, int se, int si) {
if (ss == se) {
leaves[ss].insert(val);
seg[si] = delt[si] + *leaves[ss].rbegin();
return;
}
int mid = (ss+se)/2;
if (ai <= mid) {
av(ai, val, ss, mid, si*2+1);
}
else av(ai, val, mid+1, se, si*2+2);
seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]);
}
void addval(int ai, int val) {
av(ai, val, 0, N+Q, 0);
}
void rv(int ai, int val ,int ss, int se, int si) {
if (ss == se) {
leaves[ss].erase(leaves[ss].find(val));
if (leaves[ss].size() == 0) {
seg[si] = -1234567890;
}
else {
seg[si] = delt[si] + *leaves[ss].rbegin();
}
return;
}
int mid = (ss+se)/2;
if (ai <= mid) rv(ai, val , ss, mid, si*2+1);
else rv(ai, val, mid+1, se, si*2+2);
seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]);
}
void remval(int ai, int val) {
rv(ai, val, 0, N+Q, 0);
}
void ta(int ts, int te, int diff, int ss, int se, int si) {
if (ts > te || ss > se) return;
if (ts > se || te < ss) return;
if (ts <= ss && se <= te) {
// cout << "tagging " << ss << " to " << se << " with: " << diff << endl;
delt[si] += diff;
seg[si] += diff;
return;
}
int mid = (ss+se)/2;
ta(ts, te, diff, ss, mid, si*2+1);
ta(ts, te, diff, mid+1, se, si*2+2);
seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]);
}
void tag(int ts, int te, int diff) {
// cout << "told to tag: " << ts << " to " << te << " with " << diff << endl;
ta(ts, te, diff, 0, N+Q, 0);
}
vector<int> countScans(vector<int> A,vector<int> X, vector<int> V){
fill(seg, seg+maxn*4, -12438); //random numbers
Q = X.size();
N = A.size();
set<int> nums;
int ct = 0;
for (int val : A) nums.insert(val);
for (int val : V) nums.insert(val);
for (int val : nums) {
dec[val] = ct++;
// cout << "dec stuff: " << ct-1 << " goes to " << val << endl;
}
for (int i = 0; i < N; i++) {
A[i] = dec[A[i]];
cvals[i] = A[i];
}
for (int i = 0; i < Q; i++) {
V[i] = dec[V[i]];
}
vector<int> onums;
for (int val : A) onums.push_back(val);
sort(onums.begin(), onums.end());
// cout << "onums: ";
// for (int val : onums) cout << val << " ";
// cout << endl;
for (int i = 0; i < maxn; i++) {
ovals[i] = upper_bound(onums.begin(), onums.end(), i)-onums.begin();
// if (i <= 5) cout << i << ": " << ovals[i] << endl;
}
for (int i = 0; i < N; i++) {
addval(A[i], i-ovals[A[i]]+1);
}
vector<int> answer(Q);
for (int i = 0; i < Q; i++) {
// cout << "doing: " << i << endl << endl;
int ci = X[i];
int vi = V[i];
int ov = cvals[ci];
cvals[ci] = vi;
remval(ov, ci-ovals[ov]+1);
addval(vi, ci-ovals[vi]+1);
tag(vi, N+Q, -1);
tag(ov, N+Q, 1);
answer[i] = query();
}
return answer;
}
