Contest

原来这题是每日一题......?这题可以用树状数组求逆序对解决,首先我们可以知道..我们把其中一维排序,另外一维按第一维的顺序插入就会产生一组答案.对于可计数的答案来说,我们考虑两种,第一种是我第一维大于它的第二维,我的第二维小于它的第二维,第三维未知但是算出来的答案重复次数只会是1,因为第三维可能是继续大于,那么只会和第二种重复,要么小于只会和第一种重复...好了,牛客的每日一题,假如我没做过,还是可以做一下的...毕竟有很多题解,对于萌新可真是太友好了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct vv{
    ll a,b,c;
}w[N];
bool cmp1(vv x,vv y)    {  return x.a<y.a;  }
bool cmp2(vv x,vv y)    {  return x.b<y.b;  }
ll n,sum[N];
ll lowbit(ll x) {  return x&(-x);  }
void add(ll pos,ll val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}
ll query(ll pos)
{
    ll res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    ll ans=0;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&w[i].a,&w[i].b,&w[i].c);
    }
    sort(w+1,w+1+n,cmp1);
    for(ll i=1;i<=n;i++)
    {
        add(w[i].b,1);
        ans+=i-query(w[i].b);
    }
    for(ll i=1;i<=n;i++)
    {
        add(w[i].b,-1);
    }
    for(ll i=1;i<=n;i++)
    {
        add(w[i].c,1);
        ans+=i-query(w[i].c);
    }
    for(ll i=1;i<=n;i++)
    {
        add(w[i].c,-1);
    }
    sort(w+1,w+1+n,cmp2);
    for(ll i=1;i<=n;i++)
    {
        add(w[i].c,1);
        ans+=i-query(w[i].c);
    }
    printf("%lld\n",ans/2);
    return 0;
}