- 1#include 2#include 3 using namespace std;
- 4 struct eve 5 {
- 6 int a,
- b,
- c,
- cont,
- ans;
- 7 bool operator == (const eve y) const 8 {
- return a == y.a && b == y.b && c == y.c;
- }
- 9
- };
- 10 eve A[100005],
- B[100005];
- 11 int tot,
- n,
- k,
- cont[200005],
- ans[100005];
- 12 void add(int p, int q) {
- for (p; p <= k; p += (p & ( - p))) cont[p] += q;
- }
- 13 int sum(int p) 14 {
- 15 int ans = 0;
- 16
- for (p; p; p -= (p & ( - p))) ans += cont[p];
- 17
- return ans;
- 18
- }
- 19 bool comp1(const eve & a, const eve & b) 20 {
- 21
- if (a.a == b.a) return a.b == b.b ? a.cb.b;
- 22
- else return a.a < b.a;
- 23
- }
- 24 bool comp2(const eve & a, const eve & b) 25 {
- return a.b == b.b ? a.cb.b;
- }
- 26 void cdq(int, int);
- 27 int main() 28 {
- 29 scanf("%d%d", &n, &k);
- 30 int i,
- j;
- 31
- for (i = 1; i <= n; i++) 32 scanf("%d%d%d", &A[i].a, &A[i].b, &A[i].c);
- 33 sort(A + 1, A + n + 1, comp1);
- 34
- for (i = 1; i <= n; i = j) 35 {
- 36 B[++tot] = A[i];
- 37
- for (j = i + 1; j <= n && A[j] == A[i]; j++);
- 38 B[tot].cont = j - i;
- 39
- }
- 40 cdq(1, tot);
- 41
- for (i = 1; i <= tot; i++) ans[B[i].ans + B[i].cont - 1] += B[i].cont;
- 42
- for (i = 0; i "%d\n", ans[i]);
- 43
- return 0;
- 44
- }
- 45 void cdq(int l, int r) 46 {
- 47
- if (l == r) return;
- 48 int mid = (l + r) >> 1;
- 49 cdq(l, mid);
- cdq(mid + 1, r);
- 50 sort(B + l, B + mid + 1, comp2);
- sort(B + mid + 1, B + r + 1, comp2);
- 51 int i = l,
- j;
- 52
- for (j = mid + 1; j <= r; j++) 53 {
- 54
- for (; i <= mid && B[i].b <= B[j].b; i++) 55 {
- add(B[i].c, B[i].cont);
- }
- 56 B[j].ans += sum(B[j].c);
- 57
- }
- 58
- for (j = l; jB[j].cont);
- 59
- }
来源: http://www.bubuko.com/infodetail-2026232.html