题意:求解a,b,c三数组中 $图片说明$ 的个数,并且(x, y), (y, x)算一组。
题解:

ANSWER1:

这个就是帖子下面好多大佬写的CDQ分治
直接求可能数不好求,那么求不符合题意得, $图片说明$ 就是不符合要求得答案
假设这种情况一共有ans种,
那么答案等于 $图片说明$
然后说一下CDQ分治,把a,b,c分成三个维度
先说一维的....直接sort
再说二维的,把第一维度进行sort,然后对于第二维度进行分治或者对第二维进行树状数组维护
下来说下三维的
对于a维度直接快排,相当于满足 $图片说明$ 的条件
再a维度快排后的基础上对于b维度进行二分分治
1.将当前处理区间分为左右两个等大的子区间；
2.递归处理左子区间；
3.处理左区间对于右区间的影响，并对于右区间或者答案进行更改与修正；
4.递归处理右子区间；
如: $图片说明$
然后分成 $图片说明$ 两个区间,对这两个区间分别进行sort排序,然后开始对两个区间进行遍历,如i在左边区间增加,j在右边区间增加
如果 $图片说明$ 那么树状数组记录当前 $图片说明$ 的数量
反之 $图片说明$ ,那么加上比当前 $图片说明$ 小的数量

//CDQ分治不咋会写......code用一下其他大佬的,code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40649892
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define maxm 200005
#define ll long long int
#define INF 0x3f3f3f3f
int n,m;
ll ans;
struct node{int x,y,z;}a[maxn],b[maxn];
bool cmp(node p,node q){
    if(p.x!=q.x)return p.x < q.x;
    if(p.y!=q.y)return p.y < q.y;
    return p.z < q.z;
}
int c[maxm];
void add(int x,int y)
{
    while(x<maxm){
        c[x]+=y;
        x+=x&(-x);
    }
}
int query(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=x&(-x);
    }
    return res;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int t=0,p1=l,p2=mid+1;
    while(p1<=mid&&p2<=r){
        if(a[p1].y<=a[p2].y){
            add(a[p1].z,1);
            b[++t]=a[p1++];
        }
        else {
            ans+=query(a[p2].z);
            b[++t]=a[p2++];
        }
    }
    while(p1<=mid){
        add(a[p1].z,1);
        b[++t]=a[p1++];
    }
    while(p2<=r){
        ans+=query(a[p2].z);
        b[++t]=a[p2++];
    }
    for(int i=l;i<=mid;i++)add(a[i].z,-1);
    for(int i=1;i<=t;i++){
        a[l+i-1]=b[i];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
    sort(a+1,a+n+1,cmp);
    cdq(1,n);
    ans=(1ll*n*(n-1)/2)-ans;
    printf("%lld\n",ans);
    return 0;
}

ANSWER2

凑成最后结果的无非就是一场大于,一场小于
另外两场大于对方相当于两场小于对方
第一场,第三场大于对方,第二场小于对方
第一场,第二场大于对方,第三场小于对方
第二场,第三场大于对方,第一场小于对方
然后相当于分别求:第一场大于对方,第二场小于对方第一场大于对方,第三场小于对方第二场大于对方,第三场小于对方
剩下的可能性是重复的......
最后ans/2
相当于上面的二维..........
第一维sort,第二维树状数组维护

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int a[maxn],b[maxn],c[maxn];
int A[maxn],B[maxn],n;
int qu(int pos){
    int ans=0;
    while(pos > 0){
        ans+=B[pos];
        pos-=(pos & (-pos));
    }
    return ans;
}
void up(int pos,int x){
    while(pos<maxn){
        B[pos]+=x;
        pos+=(pos & (-pos));
    }  

}
ll solve(int x[],int y[]){
    for(int i=0;i<n;i++)
        A[x[i]]=y[i];//桶排序
    memset(B,0,sizeof(B));
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=(i-1-qu(A[i]));
        up(A[i],1);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    ll ans=solve(a,b)+solve(a,c)+solve(b,c);
    ans/=2;
    cout<<ans<<"\n";
    return 0;
}

Contest

ANSWER1:

ANSWER2