Solution CF1093E

JWRuixi · 2022-11-01 17:16:51 · 题解

~~这个时限给的……，只要不乱搞都能过吧……~~

题意

给定排列 a,b，实现以下操作：

1 l r L R，查询即出现在 a_{[l,r]} 中，又出现在 b_{[L,R]} 中的数。
2 x y，交换 b_x 和 b_y。

分析

首先，如果将数 i 在 a 中的下标设成 x_i，将其在 b 中的下标设成 y_i，则这题可以转换为带修二维数点。

这里提供两种做法：

分块套树状数组

对 y 轴进行分块，对每个块维护一个树状数组，可以做到 O(\sqrt n \log n) 查询，O(\log n) 修改，会 TLE，怎么办呢？

考虑可以在分块数组上也套上一种树状数组类的数据结构，设第 i 块上的树状数组表示 (i-\operatorname{lowbit}(i),i] 块的树状数组搞起来。

这样子可以 O(n \log n \log(\sqrt n)) 预处理，O(\sqrt n + \log n \log(\sqrt n)) 查询，O(\log n \log(\sqrt n)) 修改，可过，而且常数很小，直接最优解。

分块加值域分块

这是一种极其暴力的算法，我想快速查询 y 在第 LL 到第 RR 块，且 x 在 l 到 r 中的点的个数，那首先想到差分，让后想到值域分块，值域 [1,10^5]，显然可过。

具体的，可以设 b_{i,j} 表示前 i 块，第 j 值域块中的点数；c_{i,j} 表示前 i 块，x = j 的点数。

那么查询的时候对边角块直接暴力，对边角值域块，用 c 查询，整块用 b 查询。修改的时候考虑将 r 移到 l，[l,r - 1] 都会增加贡献，将 r 移到 l，[l,r-1] 都会减少贡献，暴力即可。

预处理 O(n\sqrt n)，查询 O(\sqrt n)，常数巨大，修改 O(\sqrt n)，常数较小。

code

分块加树状数组：

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;

namespace IO{
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline long long read () {
        reg char ch = gh();
        reg long long x = 0;
        reg char t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? -x : x;
    }
    inline void write(long long x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
}

using IO::read;
using IO::write;

const int maxn(2e5 + 500), maxk(450);
int n, m, sqn, len, a[maxn], b[maxn], X[maxn], id[maxn];

struct BIT {
    int tr[maxn];
#define lowbit(x) (x & (-x))
    inline void mdy (int x, int v) {
        for (; x <= n; x += lowbit(x)) tr[x] += v;
    }
    inline int query (int x) {
        int res = 0;
        for (; x; x -= lowbit(x)) res += tr[x];
        return res;
    }
    inline int qry (int l, int r) {
        return query(r) - query(l - 1);
    }
} tr[maxk];

inline int qry (int x, int l, int r) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += tr[x].qry(l, r);
    return res;
}

int main () {
    n = read(), m = read(), sqn = sqrt(n), len = (n - 1) / sqn + 1;
    for (int i = 1; i <= n; i++) a[i] = read(), X[a[i]] = i;
    for (int i = 1; i <= n; i++) b[i] = read();
    for (int i = 1; i <= n; i++) id[i] = (i - 1) / sqn + 1;
    for (int i = 1, now = 1; now <= len; now++) {
        for (; id[i] == now; i++) {
            for (int j = now; j <= len; j += lowbit(j))
                tr[j].mdy(X[b[i]], 1);
        }
    }
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int l = read(), r = read(), L = read(), R = read(), res = 0;
            int ll = id[L], rr = id[R];
            if (ll == rr) {
                for (int i = L; i <= R; i++) if (l <= X[b[i]] && X[b[i]] <= r) res++;
            } else {
                for (int i = L; id[i] == ll; i++) 
                    if (l <= X[b[i]] && X[b[i]] <= r) res++;
                for (int i = R; id[i] == rr; i--) 
                    if (l <= X[b[i]] && X[b[i]] <= r) res++;
                res += qry(rr - 1, l, r) - qry(ll, l, r);
            }
            write(res), puts("");
        } else {
            int l = read(), r = read(), ll = id[l], rr = id[r];
            for (int x = ll; x <= len; x += lowbit(x)) tr[x].mdy(X[b[l]], -1);
            for (int x = rr; x <= len; x += lowbit(x)) tr[x].mdy(X[b[r]], -1);
            for (int x = ll; x <= len; x += lowbit(x)) tr[x].mdy(X[b[r]], 1);
            for (int x = rr; x <= len; x += lowbit(x)) tr[x].mdy(X[b[l]], 1);
            swap(b[l], b[r]);
        }
    }
}

分块加值域分块：

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;

namespace IO{
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline long long read () {
        reg char ch = gh();
        reg long long x = 0;
        reg char t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? -x : x;
    }
    inline void write(long long x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
}

using IO::read;
using IO::write;

const int maxn(2e5 + 50), maxk(450);
int n, m, sqn, len, x[maxn], y[maxn], pb[maxn], id[maxn], b[maxk][maxk], c[maxk][maxn];

int main () {
    n = read(), m = read(), sqn = sqrt(n), len = (n - 1) / sqn + 1;
    for (int i = 1; i <= n; i++) id[i] = (i - 1) / sqn + 1;
    for (int i = 1; i <= n; i++) x[i] = read(), pb[x[i]] = i;
    for (int i = 1; i <= n; i++) y[i] = read();
    for (int now = 1, i = 1; now <= len; now++) {
        for (int j = 1; j <= n; j++) c[now][j] = c[now - 1][j];
        for (int j = 1; j <= len; j++) b[now][j] = b[now - 1][j];
        for (; id[i] == now; i++) {
            int v = pb[y[i]];
            b[now][id[v]]++;
            c[now][v]++;
        }
    }
    while (m--) {
        int opt = read(), l = read(), r = read();
        if (opt == 1) {
            int L = read(), R = read(), LL = id[L], RR = id[R], res = 0;
            if (LL == RR) {
                for (int i = L; i <= R; i++) if (l <= pb[y[i]] && pb[y[i]] <= r) res++;
            } else {
                int ll = id[l], rr = id[r];
                for (int i = L; id[i] == LL; i++) if (l <= pb[y[i]] && pb[y[i]] <= r) res++;
                for (int i = R; id[i] == RR; i--) if (l <= pb[y[i]] && pb[y[i]] <= r) res++;
                if (ll == rr) {
                    for (int i = l; i <= r; i++) res += c[RR - 1][i] - c[LL][i];
                } else {
                    for (int i = l; id[i] == ll; i++) res += c[RR - 1][i] - c[LL][i];
                    for (int i = r; id[i] == rr; i--) res += c[RR - 1][i] - c[LL][i];
                    for (int i = ll + 1; i < rr; i++) res += b[RR - 1][i] - b[LL][i];
                }
            }
            write(res), puts("");
        } else {
            if (l > r) swap(l, r);
            int ll = id[l], rr = id[r];
            int v = pb[y[r]];
            for (int i = ll; i < rr; i++) b[i][id[v]]++, c[i][v]++;
            v = pb[y[l]];
            for (int i = ll; i < rr; i++) b[i][id[v]]--, c[i][v]--;
            swap(y[l], y[r]);
        }
    }
}