Contest

时间限制：1秒 空间限制：131072K

题目描述

n支队伍一共参加了三场比赛。

一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。

求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。

(x, y), (y, x)算一组。

 

输入描述:

第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]，分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000

输出描述:

输出一个整数表示满足条件的(x,y)数；64bit请用lld

示例1

输入

41 3 12 2 44 1 23 4 3

输出

5

---

求三维偏序对，在二维的基础上可以进行，这个可以BIT+CDQ啊，但是超时妥妥的

超时代码

#include
           
            #include
            
             using namespace std;#define maxn 200002typedef long long ll;int T,n,tot,id[maxn];inline char _getchar(){    static const int BUFSIZE = 100001 ;    static char  buf[BUFSIZE] ;    static char  *psta=buf, *pend=buf ;    if (psta >= pend){        psta = buf;        pend = buf + fread(buf,1,BUFSIZE,stdin);        if (psta >= pend)            return -1;    }    return *psta++;}inline void read(int &x){    char c;    int ans=0;    for(c=getchar(); c<'0'||c>'9'; c=getchar());    while(c>='0'&&c<='9')        ans=(ans<<1)+(ans<<3)+(c-'0'),c=getchar();    x=ans;}struct node{    int x,y,z,cnt,ans,id;} p[maxn];int cmpx(node a,node b){    if(a.x!=b.x)return a.x
             
              >1;    CDQ(l,mid);    CDQ(mid+1,r);    sort(p+l,p+mid+1,cmpy);    sort(p+mid+1,p+r+1,cmpy);    int j=l;    for(int i=mid+1; i<=r; i++)    {        for(; j<=mid&&p[j].y<=p[i].y; j++)            bit.update(p[j].z,p[j].cnt);        p[i].ans+=bit.query(p[i].z);    }    for(int i=l; i
             
            
           

为什么要CDQ啊，严重拖慢了时间啊，但是扔到CF上是可以AC的，谁让CF的机器跑的快呢

附上AC代码

#include
           
            using namespace std;#define LL long longconst int maxn=200005;const int K = 450;struct Point{    int x,y,z;    bool operator < (const Point& rhs) const {
         return z
            
             p[i].x-(p[i].x%K);j--) if(Y[j]
             
              p[i].y-(p[i].y%K);j--) if(X[j]<=p[i].x-(p[i].x%K)) ans--;        X[p[i].y]=p[i].x,Y[p[i].x]=p[i].y;        modify1D((p[i].x+K-1)/K,(p[i].y+K-1)/K,1);    }    printf("%lld\n",ans);}