分析:
给定n个二元组，求选出两个二元组(可以是同一个)组成一序列其LIS为1,2,3,4的方法数。
分别记为s1, s2, s3, s4
s1,s4对应的情形为a >= b >= c >= d, a < b < c < d，易求
长度为3时，先求得s3 + s4的值，分解为两种情况的和减去两种情况的并，min(a, b) < c < d, a < b < max(c, d)，减去a < min(b, c) <= max(b, c) < d的方法数(使用二位树状数组，只考虑x[i] < y[i]),此时方法数为s3 + s4,减去s4得s3
总数为n * n,减去其他情况即为s2
若有更好的解法请指出！
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 100008;
int C[1018];
int x[N], y[N]; inline int lowbit(int x){
return x&-x;
}
void add(int x, int n){//将第x个数增加val，从1计数
for(int i=x;i<=n;i+=lowbit(i)){
C[i]++;
}
}
int sum(int x){//求1到x的和
int ret = 0;
for(int i=x;i>0;i-=lowbit(i)){
ret+=C[i];
}
return ret;
}
namespace bit{ int C[1008][1008];
inline int lowbit(int x){
return x&-x;
}
void add(int x,int y,int n){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)) {
C[i][j]++;
}
}
} int sum(int x,int y){
int ret=0;
for(int i=x;i>0;i-=lowbit(i)) {
for(int j=y;j>0;j-=lowbit(j)) {
ret+=C[i][j];
}
}
return ret;
}
LL solve(int n){
LL ans = 0;
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
ans += sum(x[i] - 1, y[i] - 1);
}
}
return ans;
} } int main(){
int n, m;
while(~scanf("%d %d", &n, &m)){
memset(bit::C, 0, sizeof(bit::C));
int tot = 0;
for(int i = 1; i <= n; i++){
scanf("%d %d", &x[i], &y[i]);
if(x[i] < y[i]){
bit::add(x[i], y[i], m);
}
}
LL s1 = 0, s2 = 0, s3 = 0, s4 = 0;
//s4
memset(C, 0, sizeof(C));
for(int i = 1; i<= n; i++){
if(x[i] < y[i]){
add(y[i], m);
}
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s4 += sum(x[i] - 1);
}
}
//s3 + s4
memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++){
add(min(x[i], y[i]), m);
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s3 += sum(x[i] - 1);
}
} memset(C, 0, sizeof(C));
for(int i = 1; i <= n; i++){
add(max(x[i], y[i]), m);
}
for(int i = 1; i <= n; i++){
if(x[i] < y[i]){
s3 += n - sum(y[i]);
}
} s3 -= bit::solve(n);
s3 -= s4; //s1
memset(C, 0, sizeof(C));
tot = 0;
for(int i = 1; i <= n; i++){
if(x[i] >= y[i]){
tot++;
add(y[i], m);
}
}
for(int i = 1; i <= n; i++){
if(x[i] >= y[i]){
s1 += tot - sum(x[i] - 1);
}
}
s2 = (LL)n * n - s1 - s3 - s4;
printf("%I64d %I64d %I64d %I64d\n", s1, s2, s3, s4);
} return 0;
}