Contest

做法

这题做法还是比较明显的。既然直接计算答案麻烦，可以把题目转化为所有方案数减去比强而不比强的方案数，说白了就是个三维偏序模板题。

CDQ分治

用来求三维偏序，简单来说就是在二维为偏序的基础上加上对时间这一维的分治，类似于整体二分。

CODE

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define I inline
#define ri register int
#define lowbit(x) x & -x
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
    int s = 0 , w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int N = 1e6 + 5;
struct Node {
    int a , b , c, ans;
} a[N];

I bool cmp_abc(Node A , Node B) {
    if(A.a != B.a) return A.a < B.a;
    if(A.b != B.b) return A.b < B.b;
    return A.c < B.c;
} 

I bool cmp_b(Node A , Node B) {
    return A.b < B.b;
}

I bool operator != (const Node &A , const Node &B) {
    return (A.a != B.a) || (A.b != B.b) || (A.c != B.c) ;
} 

int n , k , cnt[N] , c[N] ;
ll Ans;

I void modify(int x , int w) {
    while(x <= n) c[x] += w , x += lowbit(x);
}

I int query(int i) {
    int res = 0;
    for( ; i ; i -= lowbit(i)) res += c[i];
    return res;
}

void solve(int l , int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    solve(l , mid) ; solve(mid + 1 , r);
    sort(a + l , a + mid + 1 , cmp_b);
    sort(a + mid + 1 , a + r + 1 , cmp_b);
    int j = l ;
    For(i , mid + 1 , r) {
        while(j <= mid && a[j].b <= a[i].b) {
            modify(a[j].c , 1);
            ++ j;
        }
        a[i].ans += query(a[i].c);
    }
    while(-- j >= l) modify(a[j].c , - 1);
}
signed main() {
    freopen("in.cpp" , "r" , stdin);
    freopen("out.cpp" , "w" , stdout);
    n = read() ;
    For(i , 1 , n) a[i].a = read() , a[i].b = read() , a[i].c = read();
    sort(a + 1 , a + n + 1 , cmp_abc);
    for(int i = n , j = n ; i >= 1 ; -- i) {
        while(a[j] != a[i]) -- j ;
        a[i].ans += j - i;
    }
    solve(1 , n) ; 
    For(i , 1 , n) Ans += a[i].ans ; 
    cout << n * 1ll * (n - 1) / 2 - Ans << endl;
    return 0;
}