C 题题解算法一的各个档的部分分。

看着题目挺有意思，于是做了做，结果发现题解只给出了第二种做法的代码，所以几乎所有人的代码都是第二种做法，但这道题目的价值真的是得满分吗？

不难发现，出题人细心规划的部分档非常细，并且在最后的数据范围中成功卡掉了 $O(N^2\log N)$ ，所以以下都是部分分的档，正解未写出，只想到了 $O(N^2\log N)$ 的做法，若有大佬可以解答一下题解中前缀和优化是如何做，请私信我。

8 pts

对于暴力， $8$ 分好成绩，不过不是我关注的重点，重点如何DP，以及 DP 优化。

20 pts

对于 20% 的数据，有 1 ≤ n ≤ 100。

$f[i][j][i]$ 表示前 $i$ 个数，子集最后一个是 $i$ 前一个是 $j$ 的合法方案数。转移枚举 $k$ 作为更靠前的一个数。

$f[i][j][i]=\sum_{k=1}^{j-1}f[i-1][k][j]\times (1/0)$

其中 $(0/1)$ 表示是否满足题目要求。

代码

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

$36$ 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);

$76$ pts

我想了半天，只有一个树状数组维护的方法，我们给每一个点都开一颗树状数组。以各个数的排名作为下表，所以这是一颗值域树状数组。
那么他维护的含义是：在 $i$ 之前的点中，排名为 $j$ 的点对 $i$ 点做出的贡献，即 $f[j][i]$ 。
那么我们每次 $n^2$ 枚举 $i,j$ ,那么对于第三位 $K$ 考虑用树状数组去做，我们发现满足要求的 $K$ 有一个性质是要与 $i$ 的权值作比较，我们先比较 $i,j$ 大小，在判定 $k$ 是找小于 $i$ 的，还是大于 $i$ 的，这个找的过程，其实就是在第 $j$ 颗树状数组中查出 $i$ 的前驱或者后记的 $f[k][j]$ 总价值。总时间复杂度 $O(N^2\log N)$ 。

我们发现这空间不够用，所以我们只需要开两颗树状数组，模仿着滚动数组的样子，一次清空，因为时间复杂度已经是 $O(N^2)$ 往上的级别了，所以清空完全可以承受，只会增加一点点常熟，所以可以用时间换空间。

以下是树状数组为滚动的代码

/*
树状数组优化+离散化 
*/
#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;
}