【拼十字——树状数组】

题目

暴力代码 30%

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n;
int l[N], w[N], c[N];
int main()
{
    cin >> n;

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> w[i] >> c[i];
        for (int j = 1; j < i; j++)
        {
            if (l[j] > l[i] && w[j] < w[i] && c[j] != c[i] || l[j] < l[i] && w[j] > w[i] && c[j] != c[i])
                ans = (ans + 1) % mod;
        }
    }
    cout << ans;
}

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
struct node
{
    int l, w, c;
    bool operator<(const node &y) const
    {
        if (l != y.l)
            return l > y.l;
        return w > y.w;
    }
} a[N];
int f0[N], f1[N], f2[N], n;
void add(int x, int f[])
{
    for (; x <= 1e5; x += x & -x)
        f[x]++;
}
int query(int x, int f[])
{
    int retv = 0;
    for (; x; x -= x & -x)
        retv += f[x];
    return retv;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int l, w, c;
        cin >> l >> w >> c;
        a[i] = {l, w, c};
    }

    sort(a + 1, a + n + 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = a[i].l, w = a[i].w, c = a[i].c;
        if (c == 0)
        {
            ans = (ans + query(w - 1, f1) + query(w - 1, f2)) % mod;
            add(w, f0);
        }
        else if (c == 1)
        {
            ans = (ans + query(w - 1, f0) + query(w - 1, f2)) % mod;
            add(w, f1);
        }
        else if (c == 2)
        {
            ans = (ans + query(w - 1, f0) + query(w - 1, f1)) % mod;
            add(w, f2);
        }
    }

    cout << ans;
}