LOJ2736 回转寿司

题目蓝链

Solution

直接分块就可以了，对于每一块维护一个大根堆

每次操作对于整块的部分就直接先把待替换元素压进去，然后取出堆顶的元素

对于边界块就直接利用一个小根堆去暴力重构，然后直接依次从堆中取出最小的元素去替换就可以了，然后直接重建这个块的大根堆

时间复杂度\(\mathcal{O}(q \cdot \sqrt n \cdot log(q + \sqrt n))\)

Code

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
    int sum = 0, fg = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) fg = -1;
    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
    return fg * sum;
}

const int maxn = 4e5 + 10;
const int B = 577;

priority_queue<int> pq[maxn / B + 5];
int n, m, blks, a[maxn], S[maxn / B + 5][maxn], top[maxn / B + 5];

int pos(int x) { return (x - 1) / B + 1; }

void Set(int x) {
    if (x <= 0 || x > blks) return;
    priority_queue<int, vector<int>, greater<int> > now(S[x] + 1, S[x] + top[x] + 1);
    int l = (x - 1) * B + 1, r = min(x * B, n);
    for (int i = l; i <= r; i++) {
        now.push(a[i]);
        a[i] = now.top();
        now.pop();
    }
    top[x] = 0;
}

int solve(int l, int r, int v) {
    int x = pos(l), y = pos(r);
    if ((l - 1) % B == 0) --x;
    if (r % B == 0) ++y;
    if (x == y) {
        Set(x);
        for (int i = l; i <= r; i++) if (a[i] > v) swap(a[i], v);
        pq[x] = priority_queue<int>(a + (x - 1) * B + 1, a + x * B + 1);
    } else {
        Set(x), Set(y); int _l = x * B;
        for (int i = l; i <= _l; i++) if (a[i] > v) swap(a[i], v);
        pq[x] = priority_queue<int>(a + (x - 1) * B + 1, a + _l + 1);
        ++x, --y;
        for (int i = x; i <= y; i++) {
            if (pq[i].top() > v) {
                pq[i].push(v);
                S[i][++top[i]] = v;
                v = pq[i].top();
                pq[i].pop();
            }
        }
        for (int i = y * B + 1; i <= r; i++) if (a[i] > v) swap(a[i], v);
        pq[y + 1] = priority_queue<int>(a + y * B + 1, a + (y + 1) * B + 1);
    }
    return v;
}

int main() {
    freopen("in.in", "r", stdin);
    freopen("in.out", "w", stdout);

    n = read(), m = read();
    blks = (n - 1) / B + 1;

    int cnt = 0;
    for (int i = 1; i < blks; i++)
        for (int j = 1; j <= B; j++)
            pq[i].push(a[++cnt] = read());
    for (int i = (blks - 1) * B + 1; i <= n; i++)
        pq[blks].push(a[++cnt] = read());

    while (m--) {
        int l = read(), r = read(), v = read();
        if (l <= r) printf("%d\n", solve(l, r, v));
        else printf("%d\n", solve(1, r, solve(l, n, v)));
    }

    return 0;
}

Summary

其实我在考试的时候已经无限接近正解了，但是在想怎么重构块的时候卡住了。我一开始以为最终序列和操作的顺序有关，所以没想到直接把所有的操作元素放到一个小根堆里就可以了

LOJ2736 回转寿司

原文：https://www.cnblogs.com/xunzhen/p/9844547.html