QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212300 | #5409. Perotation | jrjyy | 0 | 0ms | 3788kb | C++20 | 3.2kb | 2023-10-13 14:32:41 | 2023-10-13 14:32:42 |
answer
#include <bits/stdc++.h>
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
std::vector<T> t;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
t.assign(n, T{});
}
void add(int p, const T &x) {
for (++p; p <= n; p += p & -p) {
t[p - 1] += x;
}
}
T sum(int p) const {
T x{};
for (; p; p -= p & -p) {
x += t[p - 1];
}
return x;
}
T rangeSum(int l, int r) const {
return sum(r) - sum(l);
}
};
constexpr int B = 5000;
struct Block {
std::vector<int> &a, &pos, &f;
const int l = 0, r = 0;
int sum = 0;
std::vector<int> val, delta;
Block(std::vector<int> &a_, std::vector<int> &pos_, std::vector<int> &f_, int l_, int r_)
: a{a_}, pos{pos_}, f{f_}, l{l_}, r{r_}, sum{}, val(r - l), delta(r - l) {}
void pull() {
sum = 0;
for (int i = 0; i < r - l; ++i) {
delta[i] = f[pos[val[i]]] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
sum += delta[i];
}
}
void push() {
for (int i = 0; i < r - l; ++i) {
f[pos[val[i]]] = delta[i] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
}
}
void build() {
for (int i = l; i < r; ++i) {
val[i - l] = a[i];
}
std::sort(val.begin(), val.end());
pull();
}
};
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
--a[i];
}
Fenwick<int> fen(n);
std::vector<int> pos(n), f(n);
for (int i = n - 1; i >= 0; --i) {
pos[a[i]] = i;
f[i] = fen.sum(a[i]) & 1;
fen.add(a[i], 1);
}
std::vector<Block> block;
for (int l = 0, r; l < n; l = r) {
r = std::min(l + B, n);
block.emplace_back(a, pos, f, l, r);
block.back().build();
}
auto modify = [&](int x, int y) {
if (x / B == y / B) {
block[x / B].push();
for (int i = x + 1; i < y; ++i) {
f[i] ^= (a[x] < a[i]) ^ (a[y] < a[i]);
f[x] ^= a[i] < a[x];
f[y] ^= a[i] < a[y];
}
f[x] ^= a[y] < a[x];
f[y] ^= a[x] < a[y];
std::swap(a[x], a[y]);
std::swap(pos[x], pos[y]);
std::swap(f[x], f[y]);
block[x / B].pull();
} else {
assert(false);
}
};
auto query = [&]() -> int {
int id = (n - 1) / B;
while (id >= 0 && block[id].sum == 0) {
--id;
}
if (id == -1) {
return 0;
}
block[id - 1].push();
int pos = std::min((id + 1) * B, n);
while (f[pos - 1] == 0) {
--pos;
assert(pos > id * B);
}
return pos;
};
while (q--) {
int x, y;
std::cin >> x >> y;
--x, --y;
std::tie(x, y) = std::minmax({x, y});
modify(x, y);
std::cout << query() + 1 << "\n";
}
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 10
Accepted
time: 0ms
memory: 3572kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
9 7 3 5 8 2 4 9 1 6 7 2 8 3 1 2 1 1 5 3 8 1 3 9 1
output:
7 7 7 7 7 7 7
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
7 7 6 7 2 1 5 3 4 3 1 3 1 7 5 1 6 6 5 6 1 1 7
output:
3 4 6 7 4 4 4
result:
ok 7 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
7 7 2 4 3 1 5 6 7 7 6 6 3 3 1 1 4 3 4 2 5 4 1
output:
7 6 6 6 6 6 6
result:
ok 7 numbers
Test #5:
score: -10
Runtime Error
input:
6 6 5 3 1 4 2 6 5 4 5 2 4 3 6 5 1 5 6 4
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%