QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212300#5409. Perotationjrjyy0 0ms3788kbC++203.2kb2023-10-13 14:32:412023-10-13 14:32:42

Judging History

你现在查看的是最新测评结果

  • [2023-10-13 14:32:42]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3788kb
  • [2023-10-13 14:32:41]
  • 提交

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%