【拼十字——树状数组】

题目

暴力代码 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;
}