#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
constexpr int INF = 1000000000;
struct Mn {
int value;
static Mn id() {
return Mn { -INF };
}
Mn operator + (const Mn &other) const {
return Mn { std::max(value, other.value) };
}
};
struct Ef {
int add;
static Ef id() {
return Ef { 0 };
}
Ef operator + (const Ef &other) const {
return Ef { add + other.add };
}
};
Mn operator * (const Mn &m, const Ef &e) {
return m.value == -INF ? m : Mn { m.value + e.add };
}
struct Segtree {
struct Node {
Mn m;
Ef e;
};
int size;
Vec<Node> data;
Segtree(const int n) {
for (size = 1; size < n; size <<= 1);
data.resize(2 * size, Node { Mn::id(), Ef::id() });
}
static int bit_lsb(const int x) {
return __builtin_ctz(x);
}
static int bit_width(const int x) {
return 32 - __builtin_clz(x);
}
void apply(const int k, const Ef &e) {
data[k].m = data[k].m * e;
data[k].e = data[k].e + e;
}
void fetch(const int k) {
data[k].m = data[k << 1 | 0].m + data[k << 1 | 1].m;
}
void flush(const int k) {
apply(k << 1 | 0, data[k].e);
apply(k << 1 | 1, data[k].e);
data[k].e = Ef::id();
}
void push(const int k) {
const int lsb = bit_lsb(k);
for (int d = bit_width(k); d != lsb; --d) {
flush(k >> d);
}
}
void pull(int k) {
k >>= bit_lsb(k);
while (k > 1) {
k >>= 1;
fetch(k);
}
}
void operate(int l, int r, int x) {
l += size;
r += size;
const auto lc = l;
const auto rc = r;
push(l);
push(r);
const Ef e { x };
while (l < r) {
if (l & 1) {
apply(l, e);
l += 1;
}
l >>= 1;
if (r & 1) {
r -= 1;
apply(r, e);
}
r >>= 1;
}
pull(l);
pull(r);
}
void assign(int i, int x) {
i += size;
push(i);
push(i + 1);
data[i].m = Mn { x };
pull(i);
pull(i + 1);
}
int fold() const {
return data[1].m.value;
}
int fold(int l, int r) {
l += size;
r += size;
push(l);
push(r);
Mn ret = Mn::id();
while (l < r) {
if (l & 1) {
ret = ret + data[l].m;
l += 1;
}
l >>= 1;
if (r & 1) {
r -= 1;
ret = ret + data[r].m;
}
r >>= 1;
}
return ret.value;
}
};
struct Fenwick {
Vec<int> data;
Fenwick(const int n): data(n + 1) { }
void add(int i, int x) {
for (i += 1; i < (int) data.size(); i += i & -i) {
data[i] += x;
}
}
int get(int i) {
int ret = 0;
for (; i > 0; i -= i & -i) {
ret += data[i];
}
return ret;
}
};
Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
const int N = A.size();
const int Q = X.size();
Vec<std::pair<int, int>> cmp;
cmp.reserve(N + Q);
for (int i = 0; i < N; ++i) {
cmp.emplace_back(A[i], i);
}
for (int i = 0; i < Q; ++i) {
cmp.emplace_back(V[i], X[i]);
}
std::sort(cmp.begin(), cmp.end());
cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
const auto index = [&](const int x, const int i) {
return std::lower_bound(cmp.begin(), cmp.end(), std::make_pair(x, i)) - cmp.begin();
};
const int Size = cmp.size();
Segtree seg(Size);
Fenwick fen(Size);
for (int i = 0; i < N; ++i) {
fen.add(index(A[i], i), 1);
}
for (int i = 0; i < N; ++i) {
seg.assign(index(A[i], i), i - fen.get(index(A[i], 0)));
}
Vec<int> ret(Q);
for (int i = 0; i < Q; ++i) {
seg.operate(index(A[X[i]] + 1, 0), Size, 1);
fen.add(index(A[X[i]], X[i]), -1);
seg.assign(index(V[i], X[i]), X[i] - fen.get(index(V[i], 0)));
fen.add(index(V[i], X[i]), -1);
ret[i] = seg.fold();
A[X[i]] = V[i];
}
return ret;
}
#ifdef __APPLE__
int main() {
int N, Q;
std::cin >> N >> Q;
Vec<int> A(N);
Vec<int> X(Q), V(Q);
for (auto &x: A) {
std::cin >> x;
}
for (int i = 0; i < Q; ++i) {
std::cin >> X[i] >> V[i];
}
for (auto x: countScans(A, X, V)) {
std::cout << x << '\n';
}
return 0;
}
#endif
Compilation message
bubblesort2.cpp: In member function 'void Segtree::operate(int, int, int)':
bubblesort2.cpp:83:20: warning: unused variable 'lc' [-Wunused-variable]
83 | const auto lc = l;
| ^~
bubblesort2.cpp:84:20: warning: unused variable 'rc' [-Wunused-variable]
84 | const auto rc = r;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
1516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
