解题报告

很明显至多选 $3$ 个就能构成一种方案，所以我们只需要考虑选 $1,2,3$ 个的情况就行了。

考虑不合法的情况，即物品之间有包含的情况，如：

1 1 1 | 3 2 2
2 2 2 | 2 1 1
      | 1 3 3

左边那个（一个完全包含另一个）是选 $2$ 个不合法的情况，右边那个（只要选两个，另一个被包含了）是选 $3$ 个不合法的情况。不难发现选 $2$ 个不合法的情况就是三维偏序问题，而选 $3$ 个不合法的情况只会出现在其中一个有两个位置包含另外两个的时候，是二维偏序问题。

求选 $3$ 个不合法的情况时，要对三个位置两两做二维偏序，会发现是有重复的：

1 1 1
2 2 2
3 3 3

重复的部分就是一个完全包含了另外两个，需要加回来两次。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,c[maxn+5],num[maxn+5],tp;struct data {int s[3],ID;} a[maxn+5],tem[maxn+5];LL ans;

inline void Clear(int x) {for (int i=x;i<=n;i+=i&-i) c[i]=0;}
inline void Update(int x,int tem) {for (int i=x;i<=n;i+=i&-i) c[i]+=tem;}
inline int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
void msort(int L,int R){
    if (L==R) return;int mid=L+(R-L>>1);msort(L,mid);msort(mid+1,R);
    for (int j=mid+1,i=L;j<=R;num[a[j].ID]+=Sum(a[j].s[2]),j++)
        while (i<=mid&&a[i].s[1]<=a[j].s[1]) Update(a[i++].s[2],1);
    for (int i=L;i<=mid;i++) Clear(a[i].s[2]);for (int k=L;k<=R;k++) tem[k]=a[k];
    for (int k=L,i=L,j=mid+1;k<=R;k++) a[k]=tem[(j>R||i<=mid&&tem[i].s[1]<tem[j].s[1])?i++:j++];
}
inline bool cmp(const data &a,const data &b) {return a.s[tp]<b.s[tp];}
inline LL Count(int A,int B,LL ans=0){
    tp=A;sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++) c[i]=0;
    for (int i=1,s;i<=n;i++) s=Sum(a[i].s[B]),ans+=(LL)s*(s-1)>>1,Update(a[i].s[B],1);return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);ans=n+((LL)n*(n-1)>>1)+((LL)n*(n-1)*(n-2)/6);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].s[0],&a[i].s[1],&a[i].s[2]),a[i].ID=i;
    tp=0;sort(a+1,a+1+n,cmp);msort(1,n);for (int i=1;i<=n;i++) ans-=num[i];
    ans-=Count(0,1)+Count(0,2)+Count(1,2);for (int i=1;i<=n;i++) ans+=(LL)num[i]*(num[i]-1);
    printf("%lld\n",ans);return 0;
}