#include <bits/stdc++.h>
using namespace std;
struct BIT {
int n;
vector<int> v;
BIT(int n) : n(n), v(n) {}
BIT() {}
int sum(int r) {
int res = 0;
for(; r >= 0; r = (r & (r + 1)) - 1) res += v[r];
return res;
}
int sum_r(int l) {
int r = sum(n - 1);
if(l > 0) r -= sum(l - 1);
return r;
}
void add(int idx, int x) {
for(; idx < n; idx = idx | (idx + 1)) v[idx] += x;
}
};
struct Point {
int idx;
int val;
int cnt;
int j;
};
vector<int> sol;
vector<Point> pts;
int n;
int m;
BIT t;
bool cmp1(pair<int,Point>& p1, pair<int,Point>& p2) {
if(p1.second.idx != p2.second.idx) return p1.second.idx > p2.second.idx;
if(p1.second.val != p2.second.val) return p1.second.val < p2.second.val;
return p1.first < p2.first;
}
bool cmp2(pair<int,Point>& p1, pair<int,Point>& p2) {
if(p1.second.idx != p2.second.idx) return p1.second.idx < p2.second.idx;
if(p1.second.val != p2.second.val) return p1.second.val > p2.second.val;
return p1.first < p2.first;
}
void solve1(int l, int r) {
if(l == r) return;
int mid = (l + r) / 2;
solve1(l, mid);
solve1(mid + 1, r);
vector<pair<int,Point>> tmp;
for(int i = l; i <= mid; i++) {
tmp.push_back({-1, pts[i]});
}
for(int i = mid+1; i <= r; i++) {
tmp.push_back({1, pts[i]});
}
sort(tmp.begin(), tmp.end(), cmp1);
vector<pair<int,int>> updates;
for(auto[s, p] : tmp) {
if(s == -1) {
//cout << "ADD: " << p.idx << " " << p.val << " | " << p.cnt << " " << p.j << "\n";
t.add(p.val, p.cnt);
updates.push_back({p.val, p.cnt});
} else {
//cout << "QUE: " << p.idx << " " << p.val << " | " << p.cnt << " " << t.sum(p.val - 1) << " " << p.j << "\n";
sol[p.j] += p.cnt * t.sum(p.val - 1);
}
}
//cout << "=============" << l << " " << r << "===============\n";
for(auto[idx, x] : updates) {
t.add(idx, -x);
}
}
void solve2(int l, int r) {
if(l == r) return;
int mid = (l + r) / 2;
solve2(l, mid);
solve2(mid + 1, r);
vector<pair<int,Point>> tmp;
for(int i = l; i <= mid; i++) {
tmp.push_back({-1, pts[i]});
}
for(int i = mid+1; i <= r; i++) {
tmp.push_back({1, pts[i]});
}
sort(tmp.begin(), tmp.end(), cmp2);
vector<pair<int,int>> updates;
for(auto[s, p] : tmp) {
if(s == -1) {
//cout << "ADD: " << p.idx << " " << p.val << " | " << p.cnt << " " << p.j << "\n";
t.add(p.val, p.cnt);
updates.push_back({p.val, p.cnt});
} else {
//cout << "QUE: " << p.idx << " " << p.val << " | " << p.cnt << " " << t.sum(p.val - 1) << " " << p.j << "\n";
sol[p.j] += p.cnt * t.sum_r(p.val + 1);
}
}
//cout << "=============" << l << " " << r << "===============\n";
for(auto[idx, x] : updates) {
t.add(idx, -x);
}
}
vector<int> countScans(vector<int> arr, vector<int> x, vector<int> v) {
vector<int> w = arr;
n = arr.size();
m = x.size();
for(int i : v) {
w.push_back(i);
}
sort(w.begin(), w.end());
w.resize(unique(w.begin(), w.end()) - w.begin());
for(int& i : arr) {
i = lower_bound(w.begin(), w.end(), i) - w.begin();
}
t = BIT(w.size());
sol.assign(m + 1, {});
pts.clear();
pts.reserve(n + 2 * m);
for(int i = 0; i < n; i++) {
pts.push_back({
.idx = i,
.val = arr[i],
.cnt = 1,
.j = 0,
});
}
for(int i = 0; i < m; i++) {
int a = x[i];
int b = lower_bound(w.begin(), w.end(), v[i]) - w.begin();
bool s = b < v[i];
pts.push_back({
.idx = a,
.val = arr[a],
.cnt = -1,
.j = i + 1,
});
arr[a] = b;
pts.push_back({
.idx = a,
.val = arr[i],
.cnt = 1,
.j = i + 1,
});
}
solve1(0, pts.size() - 1);
solve2(0, pts.size() - 1);
//for(int i : arr) cout << i << "\n";
for(int i = 1; i < sol.size(); i++) {
sol[i] += sol[i-1];
}
sol.erase(sol.begin());
return sol;
}
int main() {
vector<int> arr = {1, 2, 3, 4};
vector<int> x = {0, 2};
vector<int> v = {3, 1};
for (int i : countScans(arr, x, v)) {
cout << i << "\n";
};
}
