// #include "bubblesort2.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
struct FenwickTree {
vector<int> tree;
int size;
FenwickTree(int n) {
size = n;
tree.resize(size);
}
void update(int pos, int value) {
for (int i = pos; i < size; i |= i + 1) {
tree[i] += value;
}
}
int query(int l, int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
res += tree[i];
}
for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
res -= tree[i];
}
return res;
}
};
vector<int> countScans(vector<int> a, vector<int> pos, vector<int> value){
int q = pos.size();
vector<int> all_values = a;
all_values.insert(all_values.end(), value.begin(), value.end());
sort(all_values.begin(), all_values.end());
all_values.resize(unique(all_values.begin(), all_values.end()) - all_values.begin());
int k = all_values.size();
map<int, int> mp;
for (int i = 0; i < k; ++i) {
mp[all_values[i]] = i;
}
for (auto& x : a) {
x = mp[x];
}
for (auto& x : value) {
x = mp[x];
}
auto count = [&]() -> int {
// the answer is maximum number of inversions for a single number
FenwickTree tree(k);
// maybe will be better to reverse the array for simplicity
int res = 0;
for (auto x : a) {
res = max(res, tree.query(x + 1, k - 1));
tree.update(x, 1);
}
return res;
};
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
a[pos[i]] = value[i];
ans[i] = count();
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (auto& x : a) {
cin >> x;
}
vector<int> pos(q), value(q);
for (int i = 0; i < q; ++i) {
cin >> pos[i] >> value[i];
}
for (auto x : countScans(a, pos, value)) {
cout << x << '\n';
}
return 0;
}
/*
4 2
1 2 3 4
0 3
2 1
*/
Compilation message
/usr/bin/ld: /tmp/ccozKtHk.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKeFGNl.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
