总结 | 2022牛客OI赛前集训营-提高组（第六场）题解

T1 我是 A 题

首先分析数据生成器可以知道，所生成的三元组一定是 $(A,y,z),(x,B,z),(x,y,C)(A,y,z),\backslash ,(x,B,z),\backslash ,(x,y,C)$ 这三种类型之一，也就是说一定有一维被点满了。

我们从这方面入手。考虑将所有三元组分成三类，对每一类单独计算。由于每一类中有一维是全部相同的，所以问题就转化成了一个二维问题。

但分开计算的同时，我们会面临两类之间的答案存在交集的问题，也就是说，不同的类计算出来的答案可能会有重复，于是我们需要考虑去重。

我们一步步来想。

为了讲述简便，我们在下文中有一些定义：

1. 下文中 “二元组 $ii$” 表示 “二元组 $(a_i,b_i)(a\_i,b\_i)$”。三元组同理。

2. 若二元组 $ii$ 不大于 二元组 $jj$，我们说二元组 $jj$ 大于二元组 $ii$，也说二元组 $ii$ 能够被二元组 $jj$ 删去。三元组同理。

3. “能被二元组 $ii$ 删去的二元组” 指初始的二元组中不大于二元组 $ii$ 的二元组。三元组同理。

4. “二元组的第一维” 指二元组 $(a,b)(a,b)$ 中的 $aa$，其他类推。三元组同理。

5. “A 类” 指第一维确定为 $AA$ 的三元组的集合，其他类推。

另在文中提到的定义如无特殊说明全文沿用，题目中的定义同样适用。

单独一类的答案

由于每一类中有一维是确定的，我们不妨以一个二元组来表示它以避开繁琐的讨论。于是问题转化为：

有一些二元组 $(a,b)(a,\; b)$，满足 $a,b,c\in \mathbb{Z},a\in [1,A],b\in [1,B]a,\; b,\; c\; \backslash in\; \backslash mathbb\{Z\},\; a\; \backslash in\; [1,\; A],\; b\; \backslash in\; [1,\; B]$。 定义一个二元组 $(a_1,b_1)(a\_1,\; b\_1)$ 不大于另一个二元组 $(a_2,b_2)(a\_2,\; b\_2)$ 当且仅当 $a_1⩽a_2,b_1⩽b_{2}a\_1\; \backslash leqslant\; a\_2,\; b\_1\; \backslash leqslant\; b\_2$。 一共有 $nn$ 次操作，每次给出一个二元组 $(u,v)(u,\; v)$，将现存二元组中所有不大于 $(u,v)(u,\; v)$ 的删除。 问经过 $n 次操作后一共删掉了多少个二元组。

这个问题是比较好处理的。一个显然的思路是将所有的二元组 $(a,b)(a,b)$ 以 $aa$ 和 $bb$ 分别为第一，第二关键字排序，并处理掉无用的二元组，之后进行计算。

所谓无用的二元组是指，对一个二元组 $ii$，如果存在二元组 $jj$，使得二元组 $ii$ 不大于 二元组 $jj$，这个时候我们说二元组 $ii$ 是无用的。原因很显然，由于二元组 $jj$ 大于二元组 $ii$，所以能够被二元组 $ii$ 删去的二元组肯定能够被二元组 $jj$ 删去。

当我们处理完之后，我们会得到一个很神奇的性质：处理后剩余的二元组中若按照其中一维升序排序，则另一维降序排列。

否则就还存在无用的二元组。

对于答案的计算，我们不妨将其放到一个平面直角坐标系上来看。我们将所有会被删除的二元组标出来，那么大概会形成这样一个类似阶梯的形状（这里并没有标记出具体的点，而是笼统地概括为一个多边形）：

而我们的答案就是它的面积乘以已经固定的那个值。而它的面积可以分割成多个矩形来看，那么答案就是：

${\sum }_{i=1}^m(a_i-a_{i-1})\times b_i\backslash sum\_\{i\; =\; 1\}^\{m\}\; (a\_i\; -\; a\_\{i\; -\; 1\})\; \backslash times\; b\_i$

代码也很简单：

void my_unique(int p){
    int sizb = 0, siza = siz[p];
    sort(a[p], a[p] + siza);// 这一句待定
    for(int i = 0; i < siza; i++){
        while(i + 1 < siza && a[p][i].x == a[p][i + 1].x) i++;
        b[sizb++] = a[p][i];
    }
    siza = 0;
    for(int i = 0; i < sizb; i++){
        while(siza != 0 && a[p][siza - 1].y < b[i].y) siza--;
        a[p][siza++] = b[i];
    }
    siz[p] = siza;
}
llt work(int p, int k){
    int sizp = siz[p];
    if(sizp == 0) return 0;
    llt res = 0;
    res += (llt)a[p][0].y * a[p][0].x;
    for(int i = 1; i < sizp; i++){
        res += (llt)a[p][i].y * (a[p][i].x - a[p][i - 1].x);
    }
    return res * k;
}

到这里你可能会想，单独一类的答案一个底面为这个图形的面积，而高为固定的那个值的一个棱柱，那么总的答案不就是把他们放在三维坐标系里然后算体积吗？想法不错，但至少以我的水平完全做不出来的，就算能做也应该会非常复杂，不建议去想。

合并在一起的答案

按照上面的方法，我们可以算出每一类的答案，而在合并的过程中我们面临着重复计算的问题。遇到这种问题，想到容斥原理是天经地义的。

如果用容斥原理做的话我们需要求出他们的交集，仔细一看，好像交集也并不好求啊？

我们直接暴力枚举。

没错，就是暴力枚举求交集，这个显然会写的，然而唯一令人疑惑的地方在于，这样的复杂度上限貌似是 $O(n^3)O(n^3)$ 的。

这确实没错，实际上也确实能够卡到这个程度，然而——数据是比较随机的。

这意味着我们在处理无用的元组之后，剩下的不会太多。于是我们直接信仰之跃。

    // A 类与 B 类的交集
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[1]; j++){
            ans -= (llt)(a[1][j].x - (j == 0 ? 0 : a[1][j - 1].x)) * (llt)(a[0][i].x - (i == 0 ? 0 : a[0][i - 1].x)) * corss(0, a[0][i].y, 0, a[1][j].y);
        }
    }
    // B 类与 C 类的交集
    for(int i = 0; i < siz[1]; i++){
        for(int j = 0; j < siz[2]; j++){
            ans -= (llt)corss(i == 0 ? 0 : a[1][i - 1].x, a[1][i].x, j == 0 ? 0 : a[2][j - 1].x, a[2][j].x) * (llt)a[2][j].y * (llt)a[1][i].y;
        }
    }
    // C 类与 A 类的交集
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[2]; j++){
            ans -= (a[2][j].x - (j == 0 ? 0 : a[2][j - 1].x)) * corss(i == 0 ? 0 : a[0][i - 1].x, a[0][i].x, 0, a[2][j].y) * (llt)a[0][i].y;
        }
    }
    // A B C 三类的交集
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[1]; j++){
            for(int k = 0; k < siz[2]; k++){
                llt l1, l2, l3;
                l1 = corss(j == 0 ? 0 : a[1][j - 1].x, a[1][j].x, k == 0 ? 0 : a[2][k - 1].x, a[2][k].x);
                if(l1 == 0) continue;
                l2 = corss(i == 0 ? 0 : a[0][i - 1].x, a[0][i].x, 0, a[2][k].y);
                if(l2 == 0) continue;
                l3 = min(a[0][i].y, a[1][j].y);
                if(l3 == 0) continue;
                ans += l1 * l2 * l3;
            }
        }
    }

时间问题

这样实际上只有 $95pts95pts$，作为强迫症患者， 我们还想拿到最后五分。

虽然我们处理无用元组之后剩余的不多，然而处理之前的总数其实还是 $nn$ 个的，而我们用 $sortsort$ 排序的时间复杂度是 $O(n\log n)O(n\backslash log\; n)$ 的，$3\times 10^{7}3\; \backslash times\; 10^7$ 的数据，带个 $\log \backslash log$ 就比较难看了。

于是搬出卡常神器：基数排序。

有人可能不明白结构体怎么才能基数排序。实际上，基数排序的思想就是将每个数拆分成多个关键字，然后基于关键字排序，而我们这里的排序规则也是按照关键字排序，所以我们按照一定的顺序将两个关键字拆开就好了。

void radix_sort(int n, node a[]){
    node *b = new node[n];
    int *cnt = new int[1 << 16];
    int mask = (1 << 16) - 1;
    node *x = a, *y = b;
    // 拆 y，即第二关键字
    for(int i = 0; i < 32; i += 16){
        for(int j = 0; j < (1 << 16); j++) cnt[j] = 0;
        for(int j = 0; j < n; j++) ++cnt[x[j].y >> i & mask];
        for(int sum = 0, j = 0; j < (1 << 16); j++){
            sum += cnt[j]; cnt[j] = sum - cnt[j];
        }
        for(int j = 0; j < n; j++) y[cnt[x[j].y >> i & mask]++] = x[j];
        swap(x, y);
    }
    // 拆 x，即第一关键字
    for(int i = 0; i < 32; i += 16){
        for(int j = 0; j < (1 << 16); j++) cnt[j] = 0;
        for(int j = 0; j < n; j++) ++cnt[x[j].x >> i & mask];
        for(int sum = 0, j = 0; j < (1 << 16); j++){
            sum += cnt[j]; cnt[j] = sum - cnt[j];
        }
        for(int j = 0; j < n; j++) y[cnt[x[j].x >> i & mask]++] = x[j];
        swap(x, y);
    }
    delete[] cnt; delete[] b;
}

那么之前代码中待定的 sort 也就要换成 radix_sort 了。

别用 vector，开 $3e73e7$ 的数组是没有问题的，vector 带大肠数。

完整代码

#include<bits/stdc++.h>
#define MAXN 30000001
using namespace std;
typedef unsigned long long ull;
typedef __int128_t llt;
struct node{ int x, y; };
int n, A, B, C;
int u[MAXN], v[MAXN], w[MAXN], siz[3];
node a[3][MAXN], b[MAXN];
llt ans;
ull Rand(ull &k1, ull &k2){
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
void GetData(){
    ull x, y;
    scanf("%d%d%d%d%llu%llu",&n,&A,&B,&C,&x,&y);
    for (int i = 1; i <= n; i++) {
        u[i] = Rand(x, y) % A + 1;
        v[i] = Rand(x, y) % B + 1;
        w[i] = Rand(x, y) % C + 1;
        if (Rand(x, y) % 3 == 0) u[i] = A;
        if (Rand(x, y) % 3 == 0) v[i] = B;
        if ((u[i] != A) && (v[i] != B)) w[i] = C;
    }
}
void print(llt x){
    if(x >= 10) print(x / 10);
    putchar(x % 10 + '0');
}
void radix_sort(int n, node a[]){
    node *b = new node[n];
    int *cnt = new int[1 << 16];
    int mask = (1 << 16) - 1;
    node *x = a, *y = b;
    for(int i = 0; i < 32; i += 16){
        for(int j = 0; j < (1 << 16); j++) cnt[j] = 0;
        for(int j = 0; j < n; j++) ++cnt[x[j].y >> i & mask];
        for(int sum = 0, j = 0; j < (1 << 16); j++){
            sum += cnt[j]; cnt[j] = sum - cnt[j];
        }
        for(int j = 0; j < n; j++) y[cnt[x[j].y >> i & mask]++] = x[j];
        swap(x, y);
    }
    for(int i = 0; i < 32; i += 16){
        for(int j = 0; j < (1 << 16); j++) cnt[j] = 0;
        for(int j = 0; j < n; j++) ++cnt[x[j].x >> i & mask];
        for(int sum = 0, j = 0; j < (1 << 16); j++){
            sum += cnt[j]; cnt[j] = sum - cnt[j];
        }
        for(int j = 0; j < n; j++) y[cnt[x[j].x >> i & mask]++] = x[j];
        swap(x, y);
    }
    delete[] cnt; delete[] b;
}
void my_unique(int p){
    int sizb = 0, siza = siz[p];
    radix_sort(siza, a[p]);
    for(int i = 0; i < siza; i++){
        while(i + 1 < siza && a[p][i].x == a[p][i + 1].x) i++;
        b[sizb++] = a[p][i];
    }
    siza = 0;
    for(int i = 0; i < sizb; i++){
        while(siza != 0 && a[p][siza - 1].y < b[i].y) siza--;
        a[p][siza++] = b[i];
    }
    siz[p] = siza;
}
llt work(int p, int k){
    int sizp = siz[p];
    if(sizp == 0) return 0;
    llt res = 0;
    res += (llt)a[p][0].y * a[p][0].x;
    for(int i = 1; i < sizp; i++){
        res += (llt)a[p][i].y * (a[p][i].x - a[p][i - 1].x);
    }
    return res * k;
}
llt corss(int l1, int r1, int l2, int r2){
    return max(min(r1, r2) - max(l1, l2), 0);
}
int main(){
    GetData();
    for(int i = 1; i <= n; i++){
        if(u[i] == A) a[0][siz[0]++] = (node){v[i], w[i]};
        else if(v[i] == B) a[1][siz[1]++] = (node){u[i], w[i]};
        else if(w[i] == C) a[2][siz[2]++] = (node){u[i], v[i]};
    }
    my_unique(0); my_unique(1); my_unique(2);
    ans += work(0, A); ans += work(1, B); ans += work(2, C);
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[1]; j++){
            ans -= (llt)(a[1][j].x - (j == 0 ? 0 : a[1][j - 1].x)) * (llt)(a[0][i].x - (i == 0 ? 0 : a[0][i - 1].x)) * corss(0, a[0][i].y, 0, a[1][j].y);
        }
    }
    for(int i = 0; i < siz[1]; i++){
        for(int j = 0; j < siz[2]; j++){
            ans -= (llt)corss(i == 0 ? 0 : a[1][i - 1].x, a[1][i].x, j == 0 ? 0 : a[2][j - 1].x, a[2][j].x) * (llt)a[2][j].y * (llt)a[1][i].y;
        }
    }
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[2]; j++){
            ans -= (a[2][j].x - (j == 0 ? 0 : a[2][j - 1].x)) * corss(i == 0 ? 0 : a[0][i - 1].x, a[0][i].x, 0, a[2][j].y) * (llt)a[0][i].y;
        }
    }
    for(int i = 0; i < siz[0]; i++){
        for(int j = 0; j < siz[1]; j++){
            for(int k = 0; k < siz[2]; k++){
                llt l1, l2, l3;
                l1 = corss(j == 0 ? 0 : a[1][j - 1].x, a[1][j].x, k == 0 ? 0 : a[2][k - 1].x, a[2][k].x);
                if(l1 == 0) continue;
                l2 = corss(i == 0 ? 0 : a[0][i - 1].x, a[0][i].x, 0, a[2][k].y);
                if(l2 == 0) continue;
                l3 = min(a[0][i].y, a[1][j].y);
                if(l3 == 0) continue;
                ans += l1 * l2 * l3;
            }
        }
    }
    print(ans);
    printf("\n");
}