当前位置：首页 > news >正文

BZOJ4939 [YNOI2016]掉进兔子洞

news 来源：原创 2024/5/1 7:20:28

题目蓝链

Solution

首先，很显然这题是要用莫队来处理的。我们先把输入的数字另外排一下序，然后记录一下$p_i$表示每一个数字对应在排好序的数列里面是排第几个。询问的时候要把一个询问拆成$3$个询问，然后再并起来。然后在莫队的时候记录$cnt_i$表示当前数字$i$出现的次数，再开一个$bitset$，假设当前需要加入$bitset$的数字是$x$，我们就令$bitset$中的第$p_x + cnt_x$位为$1$，然后$++cnt_x$。这样就会使得把三个$bitset$并起来之后，恰好剩下的就是在三个区间都出现了的数字，也就是需要删除的数字，我们就只需要看并起来之后还剩多少个$1$就行了

还有一个问题，就是我们必须要对每一个询问(拆之前)都要开一个$bitset$来存答案，但这会开不下。所以我们就要平衡一下空间复杂度和时间复杂度，把询问分为几块来处理

所以其实我的程序还可以更快一些，那就是在给所有的块排好序之后再分块。但这样写起来有点麻烦，所以我就懒得卡了

Code

#include <bits/stdc++.h>

using namespace std;

#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 = 1e5 + 10;
const int maxm = 33333 + 10;

bitset<maxn> s[maxm];

int len;
struct node {
    int l, r, id;
    bool operator < (const node &t) const {
        if (l / len == t.l / len) return r < t.r;
        return l < t.l;
    }
}op[maxn];

int n, m, top, a[maxn], t[maxn], sum[maxn], cnt[maxn];

void solve(int q) {
    top = 0;
    for (int i = 1; i <= q; i++) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read(), x3 = read(), y3 = read();
        sum[i] = y1 - x1 + y2 - x2 + y3 - x3 + 3;
        op[++top] = (node){x1, y1, i}, op[++top] = (node){x2, y2, i}, op[++top] = (node){x3, y3, i};
        s[i].set();
    }
    sort(op + 1, op + top + 1);

    int l = 1, r = 0;
    static bitset<maxn> now; now.reset();
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= top; i++) {
        int x = op[i].l, y = op[i].r, id = op[i].id;
        while (l > x) {
            --l;
            now.flip(a[l] + cnt[a[l]]);
            ++cnt[a[l]];
        }
        while (r < y) {
            ++r;
            now.flip(a[r] + cnt[a[r]]);
            ++cnt[a[r]];
        }
        while (l < x) {
            --cnt[a[l]];
            now.flip(a[l] + cnt[a[l]]);
            ++l;
        }
        while (r > y) {
            --cnt[a[r]];
            now.flip(a[r] + cnt[a[r]]);
            --r;
        }
        s[id] &= now;
    }

    for (int i = 1; i <= q; i++) printf("%d\n", sum[i] - s[i].count() * 3);
}

int main() {
#ifdef xunzhen
    freopen("bitset.in", "r", stdin);
    freopen("bitset.out", "w", stdout);
#endif

    n = read(), m = read(); len = sqrt(n);
    for (int i = 1; i <= n; i++) t[i] = a[i] = read();
    sort(t + 1, t + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(t + 1, t + n + 1, a[i]) - t;

    while (m) {
        int x = min(m, 33334);
        solve(x), m -= x;
    }

    return 0;
}