折线统计(line)

折线统计(line)

题目描述

 

二维平面上有n个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。

 

现给定k，求满足f(S) = k的S集合个数。

 

 

输入

 

第一行两个整数n和k，以下n行每行两个数(xi, yi)表示第i个点的坐标。所有点的坐标值都在[1, 100000]内，且不存在两个点，x坐标值相等或y坐标值相等。

 

输出

 

 输出满足要求的方案总数 mod 100007的结果。

---

solution

令f[i][j][0/1]表示前i个点，连成j段线，最后一段上升下降的方案数

由于每次取的是一段连续的y，可以用树状数组优化

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mod 100007
using namespace std;
int n,k,tree[100005][11][2],f[50005][11][2],Max,ans;
struct node{
    int x,y;
}s[50005];
bool cmp(const node &a,const node &b){
    return a.x<b.x;
}
void jia(int i,int j,int p,int v){
    for(;i<=Max;i+=i&-i)tree[i][j][p]=(tree[i][j][p]+v)%mod;
}
int ask(int i,int j,int p){
    int sum=0;
    for(;i;i-=i&-i)sum=(sum+tree[i][j][p])%mod;
    return sum;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&s[i].x,&s[i].y);
        Max=max(Max,s[i].y);
    }
    Max++;
    sort(s+1,s+n+1,cmp);    
    for(int i=1;i<=n;i++){
        f[i][0][0]=f[i][0][1]=1;
        for(int j=1;j<=k;j++){
            f[i][j][0]=(ask(s[i].y,j,0)+ask(s[i].y,j-1,1))%mod;
            f[i][j][1]=(ask(Max,j,1)-ask(s[i].y,j,1))%mod+(ask(Max,j-1,0)-ask(s[i].y,j-1,0))%mod;
            f[i][j][1]%=mod;
        }
        ans=(ans+f[i][k][0]+f[i][k][1])%mod;
        for(int j=0;j<=k;j++){
            jia(s[i].y,j,0,f[i][j][0]);jia(s[i].y,j,1,f[i][j][1]);
        }
    }
    ans=(ans%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}