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