C 题题解算法一的各个档的部分分。
看着题目挺有意思，于是做了做，结果发现题解只给出了第二种做法的代码，所以几乎所有人的代码都是第二种做法，但这道题目的价值真的是得满分吗？
不难发现，出题人细心规划的部分档非常细，并且在最后的数据范围中成功卡掉了 ，所以以下都是部分分的档，正解未写出，只想到了
的做法，若有大佬可以解答一下题解中前缀和优化是如何做，请私信我。
8 pts
对于暴力， 分好成绩，不过不是我关注的重点，重点如何DP，以及 DP 优化。
20 pts
对于 20% 的数据，有 1 ≤ n ≤ 100。
表示前
个数，子集最后一个是
前一个是
的合法方案数。转移枚举
作为更靠前的一个数。
其中 表示是否满足题目要求。
代码
int f[B][B][B];
struct node{int x,y;} a[B];
int n;
int cmp(node a,node b)
{
return a.y>b.y;
}
signed main()
{
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i].x;
cin>>a[i].y;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for (int i=3;i<=n;i++)
for (int j=1;j<=i-1;j++)
{
for (int k=1;k<=j-1;k++) f[i][j][i]=(f[i][j][i]+(f[i-1][k][j]+1)*((a[i].x<max(a[j].x,a[k].x)&&a[i].x>min(a[j].x,a[k].x)) ? 1 : 0))%mod;
for (int k=1;k<=j-1;k++) f[i][k][j]=(f[i-1][k][j])%mod;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=i-1;j++) ans=(ans+f[n][j][i])%mod;
printf("%lld",(ans+(n*(n-1)/2)+n)%mod);
return 0;
} 
pts
我们发现可以滚动数组，把第一位滚掉就可
for (int i=3;i<=n;i++)
for (int j=1;j<=i-1;j++)
{
for (int k=1;k<=j-1;k++) f[j][i]=(f[j][i]+(f[k][j]+1)*((a[i].x<max(a[j].x,a[k].x)&&a[i].x>min(a[j].x,a[k].x)) ? 1 : 0))%mod;
for (int k=1;k<=j-1;k++) f[k][j]=f[k][j]%mod;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=i-1;j++)
ans=(ans+f[j][i])%mod;
printf("%lld",(ans+(n*(n-1)/2)+n)%mod); 
pts
我想了半天，只有一个树状数组维护的方法，我们给每一个点都开一颗树状数组。以各个数的排名作为下表，所以这是一颗值域树状数组。
那么他维护的含义是：在 之前的点中，排名为
的点对
点做出的贡献，即
。
那么我们每次 枚举
,那么对于第三位
考虑用树状数组去做，我们发现满足要求的
有一个性质是要与
的权值作比较，我们先比较
大小，在判定
是找小于
的，还是大于
的，这个找的过程，其实就是在第
颗树状数组中 查出
的前驱或者后记的
总价值。总时间复杂度
。
我们发现这空间不够用，所以我们只需要开两颗树状数组，模仿着滚动数组的样子，一次清空，因为时间复杂度已经是 往上的级别了，所以清空完全可以承受，只会增加一点点常熟，所以可以用时间换空间。
以下是树状数组为滚动的代码
/*
树状数组优化+离散化
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int B=6009;
int f[B][B];
struct node{int x,y;} a[B];
int n;
int b[B];
int t[6009][6009];
int lowbit(int x) {return x&(-x);}
void modify(int x,int v,int t1[]) {while (x<=n) t1[x]+=v,x+=lowbit(x);}
int query(int x,int t1[]) {int res=0; while (x) res+=t1[x],x-=lowbit(x);return res;}
namespace ne
{
int t[6009][6009];
void modify(int x,int v,int t1[]) {while (x<=n+10) t1[x]+=v,x+=lowbit(x);}
int query(int x,int t1[]) {int res=0; while (x) res+=t1[x],x-=lowbit(x);return res;}
}
int cmp(node a,node b)
{
return a.y>b.y;
}
int newnum[6009];
signed main()
{
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i].x;
cin>>a[i].y;
b[i]=a[i].x;
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n);
for (int i=1;i<=n;i++)
{
newnum[i]=lower_bound(b+1,b+1+n,a[i].x)-b;
}
int ans=0;
ne::modify(newnum[1],1,ne::t[2]);
for (int i=3;i<=n;i++)
{
int st=newnum[i];
ne::modify(newnum[1],1,ne::t[i]);
for (int j=2;j<=i-1;j++)
{
if (a[i].x>a[j].x)
{
f[j][i]=((query(n,t[j])-query(st,t[j]))%mod+mod)%mod;
f[j][i]=(f[j][i]+ne::query(n,ne::t[j])-ne::query(st,ne::t[j])+mod)%mod;
modify(newnum[j],f[j][i],t[i]);
ne::modify(newnum[j],1,ne::t[i]);
}
else
{
f[j][i]=query(st-1,t[j])%mod;
f[j][i]=(f[j][i]+ne::query(st-1,ne::t[j]))%mod;
modify(newnum[j],f[j][i],t[i]);
ne::modify(newnum[j],1,ne::t[i]);
}
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=i-1;j++)
ans=(ans+f[j][i])%mod;
printf("%lld",(ans+(n*(n-1)/2)+n)%mod);
return 0;
}
