CF12D-Ball

2022-03-14 题解

题目大意：第i个物品有三个属性 $A_i,B_i,C_i$ ，问有多少个物品 $i$ ，使得存在 $j$ ，使得 $A_i<A_j,B_i<B_j,C_i<C_j$ 。

首先考虑：如果每个物品只有两个属性A、B，应如何求解？不难想到，只要按照A从大到小的顺序处理每个物品，每次找出之前处理过的点物品的最大B值，判断它是否大于当前点的B值。由于之前处理过的点的A值都大于当前点的A值，所以只要那个最大B值大于当前点的B值，就说明当前物品存在A、B都比它大的物品，应记录下来。

当物品拥有三个属性，按照上面的思路可以得知大概的求解方法：按照A从大到小的顺序处理每个物品，每次找出之前处理过，且B值比当前点的B值大的物品所能取得的最大C值，并判断这个最大的C值是否比当前物品的C值大。如果这个值比当前物品的C值大，就说明当前物品存在A、B、C都比它大的物品，应记录下来。

用树状数组维护之前处理过，且B值比当前物品的B值大的物品所能取得的最大C值，就可以将整个程序的复杂度优化到可以接受的范围内。由于需要维护的物品是B值比当前大的物品，跟之前做过的其它题不一样，这里的树状数组维护的是前缀上的信息了，而是后缀上的信息。维护后缀信息，只需对树状数组进行很少程度的改动，具体会在下面的代码中体现。

另外，为避免树状数组过长，使用树状数组维护上述的那个值之前需要将B的值离散化。具体见下面的代码。

#include <bits/stdc++.h>
using namespace std;
int bit[500005], n;
struct node
{
    int a, b, c;
    bool operator<(const node &x) const
    {
        return a > x.a;
    }
} a[500005];
int lowbit(int x) { return x & -x; }

int mx(int pos)
{
    int ret = -1;
    //此处的bit[x]表示：以x为头，长度为lowbit(x)的后缀的最大值
    //因此取最大值应与普通树状数组反向操作
    while (pos <= n)
    {
        ret = max(ret, bit[pos]);
        pos += lowbit(pos);
    }
    return ret;
}

void add(int pos, int x)
{
    //取最值时在树状数组上进行了反向操作，更新结点时父节点的方向在数组上也相反了
    //因此也需与普通树状数组反向操作
    while (pos > 0)
    {
        bit[pos] = max(bit[pos], x);
        pos -= lowbit(pos);
    }
}

int main()
{
    int i, m, j, res = 0;
    vector<int> t;
    t.push_back(-1);
    scanf("%d", &m);

    for (i = 1; i <= m; i++)
        scanf("%d", &a[i].a);
    for (i = 1; i <= m; i++)
    {
        scanf("%d", &a[i].b);
        t.push_back(a[i].b);
    }
    for (i = 1; i <= m; i++)
        scanf("%d", &a[i].c);
    //将b离散化
    sort(t.begin() + 1, t.end());
    n = unique(t.begin() + 1, t.end()) - t.begin() - 1;
    for (i = 1; i <= m; i++)
        a[i].b = lower_bound(t.begin() + 1, t.begin() + 1 + n, a[i].b) - t.begin();

    sort(a + 1, a + 1 + m);
    for (i = 1; i <= m; i++)
    {
        for (j = i; j <= m && a[j].a == a[i].a; j++)
        {
            //mx(a[j].b+1)：之前处理过，且B值比当前点的B值大的物品所能取得的最大C值
            if (mx(a[j].b + 1) > a[j].c)
                res++;
        }
        for (j = i; j <= m && a[j].a == a[i].a; j++)
            add(a[j].b, a[j].c);
        i = j - 1;
    }
    printf("%d", res);
    return 0;
}