#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
struct lazy_segtree {
int n;
vector<int> tree, lazy;
lazy_segtree(int n_) : n(n_), tree(4*n_, -INF), lazy(4*n_) {}
void propagate(int node, int node_left, int node_right) {
if (lazy[node] == 0) return;
if (node_left != node_right) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0;
}
void update(int left, int right, int val, int node, int node_left, int node_right) {
propagate(node, node_left, node_right);
if (right < node_left || node_right < left) return;
if (left <= node_left && node_right <= right) {
lazy[node] = val;
propagate(node, node_left, node_right);
return;
}
int mid = (node_left + node_right) / 2;
update(left, right, val, 2*node, node_left, mid);
update(left, right, val, 2*node+1, mid+1, node_right);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
void update(int left, int right, int val) {
update(left, right, val, 1, 0, n-1);
}
int query() {
propagate(1, 0, n-1);
return tree[1];
}
int query(int pos, int node, int node_left, int node_right) {
propagate(1, 0, n-1);
if (node_left == node_right) return tree[node];
int mid = (node_left + node_right) / 2;
if (pos <= mid) return query(pos, 2*node, node_left, mid);
else return query(pos, 2*node+1, mid+1, node_right);
}
int query(int pos) {
return query(pos, 1, 0, n-1);
}
};
struct fenwick_tree {
vector<int> tree;
fenwick_tree(int n) : tree(n+1) {}
int sum(int pos) {
++pos;
int ret = 0;
while (pos > 0) {
ret += tree[pos];
pos &= (pos - 1);
}
return ret;
}
void add(int pos, int val) {
++pos;
while (pos < (int)tree.size()) {
tree[pos] += val;
pos += (pos & -pos);
}
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q;
cin >> N >> Q;
vector<ll> v(N), c(N+Q);
vector<pair<int, ll>> q(Q);
for (int i = 0; i < N; i++) {
cin >> v[i];
v[i] = v[i] * N + i;
c[i] = v[i];
}
for (int i = 0; i < Q; i++) {
cin >> q[i].first >> q[i].second;
q[i].second = q[i].second * N + q[i].first;
c[N+i] = q[i].second;
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
fenwick_tree ft((int)c.size());
for (int i = 0; i < N; i++) {
auto it = lower_bound(c.begin(), c.end(), v[i]);
v[i] = it - c.begin();
ft.add(v[i], 1);
}
for (int i = 0; i < Q; i++) {
auto it = lower_bound(c.begin(), c.end(), q[i].second);
q[i].second = it - c.begin();
}
lazy_segtree seg((int)c.size() + 1);
for (int i = 0; i < N; i++) {
seg.update(v[i], v[i], i - ft.sum(v[i]-1) + INF);
}
for (auto [pos, val] : q) {
seg.update(v[pos], v[pos], -INF - seg.query(v[pos]));
ft.add(v[pos], -1);
seg.update(v[pos]+1, (int)c.size() + 1, 1);
v[pos] = val;
ft.add(v[pos], 1);
seg.update(v[pos]+1, (int)c.size() + 1, -1);
seg.update(v[pos], v[pos], pos - ft.sum(v[pos]-1) - seg.query(v[pos]));
cout << seg.query() << '\n';
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc0YollJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4EmyoK.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc0YollJ.o: in function `main':
grader.cpp:(.text.startup+0x181): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
