pair-pair

输入文件：pair-pair.in 输出文件：pair-pair.out 简单对比
时间限制：7 s
内存限制：64 MB

Time Limit : 7000 MS

Memory Limit : 65536 KB

Pair-Pair

Bobo is tired of all kinds of hard LIS (Longest Increasing Subsequence) problems, so he decides to make himself some easier one.

Bobo has n pairs (a1,b1),(a2,b2),…,(an,bn) where 1≤ai,bi≤m holds for all
i. He defines f(i,j) be the length of longest increasing subsequence of
sequence {ai,bi,aj,bj}.

It's clear that 1≤f(i,j)≤4. Bobo would like to know g(k) which is the number of pairs (i,j) where f(i,j)=k.

Note that a sequence labeled with {i1,i2,…,ik} is an increasing subsequence of {a1,a2,…,an} only if:

1≤i1<i2<⋯<ik≤nai1<ai2<⋯<aik

Input

The first line contains 2 integers n,m (1≤n≤105,1≤m≤103).

The i-th of the following n lines contains 2 integers ai,bi (1≤ai,bi≤m).

Output

For each set, 4 integers g(1),g(2),g(3),g(4).

Sample Input

2 4

1 2

3 4

2 1

1 1

Sample Output

0 3 0 1

4 0 0 0

　　注意各种特判就好了。

　　有时间再更新题解吧……

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m;

 long long a[];

 long long b1[maxm],b2[maxm];

 long long b3[maxm],b4[maxm];

 struct Node{

     int a,b;

     Node(int a_=,int b_=){

         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=;

     while(x){

         ret+=b[x];

         x-=x&(-x);

     }

     return ret;

 }

 int rt[maxm],sum[maxn*],ch[maxn*][],cnt;

 void Insert(int pre,int &rt,int l,int r,int g,int d){

     rt=++cnt;

     ch[rt][]=ch[pre][];

     ch[rt][]=ch[pre][];

     sum[rt]=sum[pre]+d;

     if(l==r)return;

     int mid=(l+r)>>;

     if(mid>=g)Insert(ch[pre][],ch[rt][],l,mid,g,d);

     else Insert(ch[pre][],ch[rt][],mid+,r,g,d);

 }

 int Query(int pre,int rt,int l,int r,int a,int b){

     if(a>b)return ;

     if(l>=a&&r<=b)return sum[rt]-sum[pre];

     int mid=(l+r)>>,ret=;

     if(mid>=a)ret=Query(ch[pre][],ch[rt][],l,mid,a,b);

     if(mid<b)ret+=Query(ch[pre][],ch[rt][],mid+,r,a,b);

     return ret;

 }

 void Init(){

     memset(a,,sizeof(a));cnt=;

     memset(b1,,sizeof(b1));

     memset(b2,,sizeof(b2));

     memset(b3,,sizeof(b3));

     memset(b4,,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=;i<=n;i++)

             scanf("%d%d",&p[i].a,&p[i].b);

         sort(p+,p+n+,cmp);

         for(int i=,last=;i<=n;i++){

             long long tot=*(i-),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-);

                 a[]+=tmp;tot-=tmp;

                 tmp=Bit_Query(b1,p[i].b)-Bit_Query(b1,p[i].a);

                 tmp+=Bit_Query(b2,p[i].b-)-Bit_Query(b2,p[i].a-);

                 tmp+=Bit_Query(b3,m)-Bit_Query(b3,p[i].b)+Bit_Query(b4,p[i].a-);

                 tmp+=Bit_Query(b2,m)-Bit_Query(b2,p[i].b);

                 for(int j=last+;j<p[i].a;j++)rt[j]=rt[last];

                 tmp+=Query(rt[],rt[p[i].a-],,m,p[i].b,m);

                 a[]+=tmp;tot-=tmp;

                 Insert(rt[last],rt[p[i].a],,m,p[i].b,);

                 last=p[i].a;a[]+=tot;

                 Bit_Add(b1,p[i].a,);Bit_Add(b2,p[i].b,);

             }

             else{

                 tmp=Bit_Query(b3,p[i].b)+Bit_Query(b4,m)-Bit_Query(b4,p[i].a-);

                 a[]+=tmp;tot-=tmp;

                 tmp=Bit_Query(b1,m)-Bit_Query(b1,p[i].b)+Bit_Query(b2,p[i].a-);

                 a[]+=tmp;tot-=tmp;

                 a[]+=tot;

                 Bit_Add(b3,p[i].a,);Bit_Add(b4,p[i].b,);

             }

         }

         for(int i=;i<=n;i++){

             if(p[i].a!=p[i].b)a[]+=;

             else a[]+=;

         }

         printf("%lld %lld %lld %lld\n",a[],a[],a[],a[]);

     }

     return ;

 }

巴特西

数据结构（主席树,Bit）：XTU 1247/COGS 2344. pair-pair

pair-pair

最新文章

热门文章