偏序分块+bitset

题目描述

给定一个有\(n\)个元素的序列，元素编号为\([1,n]\)，每个元素有\(k\)个属性\(p_1,p_2,p_3,...,p_k\) ，求序列中满足 \(i<j\)且 \(1 \leq t \leq k\),\(p_{t,i}<p_{t,j}\) 的数对\((i,j)\)的个数。

输入格式

第一行两个整数 \(n\)，\(k\)，表示序列长度和属性个数。

接下来\(k\) 行，每行 \(n\)个整数，第\(t\) 行第 \(i\)个数表示\(p_{t,i}\) 。

输出格式

共1行，表示满足要求的数对个数。

样例

样例输入

样例输出

数据范围与提示

对于\(30\%\)的数据\(n \leq 5000\),\(k \leq 6\)

对于\(100\%\)的数据\(1 \leq n \leq 40000\)，\(k \leq 6\)。保证对于所有元素的\(p_t\)属性组成一个\(1 - n\)的排列。

分析

这道题算上坐标的话，维数达到了\(7\)维

如果用一些数据结构去维护的话，很可能会超时

其实我们用 \(bitset\) 就可以搞定这道题

对于每一维，我们用 \(bitset\) 去存储小于\(i\)的数所在的位置

最后对于每一个位置\(i\)，我们将这几个维度作位与运算

最后统计下标小于\(i\)的位置中\(1\)的个数

这样去处理时间复杂度为\(O(n \times k)\)，空间复杂度为\(O(n^2 \times k)\)

而\(40000 \times 40000 \times 6\) 的\(bitset\)我们显然是开不下的

因此我们考虑用时间换空间

我们可以用分块的思想将时间复杂度和空间复杂度都均衡至\(O(nlogn\times k)\)

代码

#include <cstdio>

#include <bitset>

#include <cmath>

#include <iostream>

const int maxn = 4e4 + 5;

inline int read() {

    int x = 0, f = 1;

    char ch = getchar();

    while (ch < '0' || ch > '9') {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (ch >= '0' && ch <= '9') {

        x = (x << 1) + (x << 3) + (ch ^ 48);

        ch = getchar();

    }

    return x * f;

}

int n, m, a[8][maxn], rk[8][maxn], blo;

std::bitset<maxn> b[8][305], now, js, ws;

int main() {

    n = read(), m = read();

    blo = sqrt(n);

    for (int i = 1; i <= m; i++) {

        for (int j = 1; j <= n; j++) {

            a[i][j] = read();

            rk[i][a[i][j]] = j;

        }

    }

    for (int i = 1; i <= m; i++) {

        for (int j = 1; j * blo <= n; j++) {

            b[i][j] = b[i][j - 1];

            for (int k = (j - 1) * blo + 1; k <= j * blo; k++) {

                b[i][j].set(rk[i][k]);

            }

        }

    }

    int ans = 0;

    ws.reset();

    for (int i = 1; i <= n; i++) {

        now.set();

        ws.set(i);

        now &= ws;

        for (int j = 1; j <= m; j++) {

            int shuyu = a[j][i] / blo;

            js.reset();

            js |= b[j][shuyu];

            for (int k = shuyu * blo + 1; k <= a[j][i]; k++) {

                js.set(rk[j][k]);

            }

            now &= js;

        }

        ans += now.count() - 1;

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

偏序分块+bitset

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

分析

代码

最新文章

热门文章

巴特西

偏序 分块+bitset

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

分析

代码

最新文章

热门文章

偏序分块+bitset