记录编号	270544	评测结果	AAAAAAAAAA
题目名称	pair-pair	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.190 s
提交时间	2016-06-14 21:49:03	内存使用	24.00 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100010;
const int maxm=1010;
int n,m;
long long a[10];
long long b1[maxm],b2[maxm];
long long b3[maxm],b4[maxm];

struct Node{
    int a,b;
    Node(int a_=0,int b_=0){
        a=a_;b=b_;
    }
}p[maxn];

bool cmp(Node x,Node y){
    if(x.a!=y.a)
    return x.a<y.a;
    return x.b<y.b;
}

void Bit_Add(long long *b,int x,int d){
    while(x<=m){
        b[x]+=d;
        x+=x&(-x);
    }
}

int Bit_Query(long long *b,int x){
    int ret=0;
    while(x){
        ret+=b[x];
        x-=x&(-x);
    }
    return ret;
}

int rt[maxm],sum[maxn*20],ch[maxn*20][2],cnt;
void Insert(int pre,int &rt,int l,int r,int g,int d){
    rt=++cnt;
    ch[rt][0]=ch[pre][0];
    ch[rt][1]=ch[pre][1];
    sum[rt]=sum[pre]+d;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(mid>=g)Insert(ch[pre][0],ch[rt][0],l,mid,g,d);
    else Insert(ch[pre][1],ch[rt][1],mid+1,r,g,d);
}

int Query(int pre,int rt,int l,int r,int a,int b){
    if(a>b)return 0;
    if(l>=a&&r<=b)return sum[rt]-sum[pre];
    int mid=(l+r)>>1,ret=0;
    if(mid>=a)ret=Query(ch[pre][0],ch[rt][0],l,mid,a,b);
    if(mid<b)ret+=Query(ch[pre][1],ch[rt][1],mid+1,r,a,b);
    return ret;
}

void Init(){
    memset(a,0,sizeof(a));cnt=0;
    memset(b1,0,sizeof(b1));
    memset(b2,0,sizeof(b2));
    memset(b3,0,sizeof(b3));
    memset(b4,0,sizeof(b4));
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("pair-pair.in","r",stdin);
    freopen("pair-pair.out","w",stdout);
#endif
	while(scanf("%d%d",&n,&m)!=EOF){
        Init();
        for(int i=1;i<=n;i++)
            scanf("%d%d",&p[i].a,&p[i].b);
        sort(p+1,p+n+1,cmp);
        for(int i=1,last=0;i<=n;i++){
            long long tot=2*(i-1),tmp;
            
            if(p[i].a<p[i].b){
                tmp=Bit_Query(b1,m)-Bit_Query(b1,p[i].b)+Bit_Query(b2,p[i].a-1);
                a[4]+=tmp;tot-=tmp;
                
                tmp=Bit_Query(b1,p[i].b)-Bit_Query(b1,p[i].a);
                tmp+=Bit_Query(b2,p[i].b-1)-Bit_Query(b2,p[i].a-1);
                
                tmp+=Bit_Query(b3,m)-Bit_Query(b3,p[i].b)+Bit_Query(b4,p[i].a-1);
                tmp+=Bit_Query(b2,m)-Bit_Query(b2,p[i].b);
                for(int j=last+1;j<p[i].a;j++)rt[j]=rt[last];
                
                tmp+=Query(rt[0],rt[p[i].a-1],1,m,p[i].b,m);
                
                a[3]+=tmp;tot-=tmp;
                
                Insert(rt[last],rt[p[i].a],1,m,p[i].b,1);
                
                last=p[i].a;a[2]+=tot;
                
                Bit_Add(b1,p[i].a,1);Bit_Add(b2,p[i].b,1);
            }
            else{
                tmp=Bit_Query(b3,p[i].b)+Bit_Query(b4,m)-Bit_Query(b4,p[i].a-1);
                a[1]+=tmp;tot-=tmp;
                
                tmp=Bit_Query(b1,m)-Bit_Query(b1,p[i].b)+Bit_Query(b2,p[i].a-1);
                a[3]+=tmp;tot-=tmp;
                
                a[2]+=tot;
                Bit_Add(b3,p[i].a,1);Bit_Add(b4,p[i].b,1);
            }
        }

        for(int i=1;i<=n;i++){
            if(p[i].a!=p[i].b)a[2]+=1;
            else a[1]+=1;
        }
        printf("%lld %lld %lld %lld\n",a[1],a[2],a[3],a[4]);
    }
    return 0;
}