Skip to content

11123: 【原1123】折线统计 Problem

题目

题目描述

author: Panzhe Yi 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1123

Description

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

1123

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

Input Format

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

Output Format

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

Sample Input 1:

5 1
5 5
3 2
4 4
2 3
1 1

Sample Output 1:

19

Sample Input 2:

5 2
5 5
3 2
4 4
2 3
1 1

Sample Output 2:

4

Limits

n<=50000, k<=10

FineArtz's solution

/* 折线统计 Problem */
#include <iostream>
using namespace std;

const int MOD = 100007;

struct Point{
    int x = 0, y = 0;

    bool operator <(const Point &p) const{
        return x < p.x;
    }
};

int n, k, maxy;
Point a[50005];
long long f[50005][11][2] = {0}, t[100005][11][2] = {0};

int lowbit(int x){
    return (x & (-x));
}

void qsort(int l, int r){
    int i = l, j = r;
    Point key = a[i];
    while (i < j){
        while (i < j && key < a[j])
            --j;
        a[i] = a[j];
        while (i < j && a[i] < key)
            ++i;
        a[j] = a[i];
    }
    a[i] = key;
    if (l < i)
        qsort(l, i - 1);
    if (r > j)
        qsort(j + 1, r);
}

void add(int x, int j, int k, long long d){
    for (int i = x; i <= maxy; i += lowbit(i))
        t[i][j][k] = (t[i][j][k] + d) % MOD;
}

long long sum(int x, int j, int k){
    long long ret = 0;
    for (int i = x; i != 0; i -= lowbit(i))
        ret = (ret + t[i][j][k]) % MOD;
    return ret;
}

int main(){
    cin >> n >> k;
    maxy = 0;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y;
        if (a[i].y > maxy)
            maxy = a[i].y;
    }
    qsort(1, n);
    for (int i = 1; i <= n; ++i){
        f[i][0][0] = 1;
        f[i][0][1] = 1;
        add(a[i].y, 0, 0, 1);
        add(a[i].y, 0, 1, 1);
        for (int j = 1; j <= k; ++j){
            f[i][j][0] += sum(a[i].y - 1, j, 0) + sum(a[i].y - 1, j - 1, 1);
            f[i][j][1] += sum(maxy, j, 1) - sum(a[i].y, j, 1) +
                          sum(maxy, j - 1, 0) - sum(a[i].y, j - 1, 0);
            f[i][j][0] = (f[i][j][0] % MOD + MOD) % MOD;
            f[i][j][1] = (f[i][j][1] % MOD + MOD) % MOD;
            add(a[i].y, j, 0, f[i][j][0]);
            add(a[i].y, j, 1, f[i][j][1]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + f[i][k][0] + f[i][k][1]) % MOD;
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

//TLE - 30

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
constexpr int mod = 100007;

vector<pii> pdata;
vector<vector<vi>> dp_data;

int n;

int dp(int pos, int k, bool dir, bool isfirst = false) {
    if (k < 0)
        return 0;
    if (dp_data[pos][k][dir])
        return dp_data[pos][k][dir];


    int ans = 0;
    if (k == 0)
        ans = 1;
    for (int nxt = pos + 1; nxt < n; ++nxt) {
        if (pdata[nxt].second < pdata[pos].second) {
            if (dir || isfirst)
                ans = (ans + dp(nxt, k - 1, false)) % mod;
            else
                ans = (ans + dp(nxt, k, false)) % mod;
        }
        else {
            if (!dir || isfirst)
                ans = (ans + dp(nxt, k - 1, true)) % mod;
            else
                ans = (ans + dp(nxt, k, true)) % mod;
        }
    }
    return dp_data[pos][k][dir] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin >> n >> k;

    pdata.resize(n);
    dp_data.resize(n, vector<vi>(k + 1, vi(2, 0)));

    for (int i = 0; i < n; ++i)
        cin >> pdata[i].first >> pdata[i].second;

    sort(pdata.begin(), pdata.end(), [](pii a, pii b) {return a.first < b.first; });
    cout << dp(0, k, false, true);

    return 0;
}

q4x3's solution

/**
 * 线段树优化dp
 * dp[i][j][0or1]表示以点i结尾的j段划分方案数(0表示最后一段上升,1表示最后一段下降)
 * 线段树按y值划分,注意应先将y值按大小映射到1-n上,方便建树
 * 这题可太nm难了
 * 虽然说可以用树状数组优化
 * 但我不会树状数组啊喂
 * 中间注释掉的部分是暴力dp
 **/
#include <iostream>

using namespace std;

struct node {
    int x, y;
};

void mergex(int lo, int mi, int hi, node* a)
{
    node* A = a + lo;
    int lb = mi - lo;
    node* B = new node[lb];
    node* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    node* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0].x < C[0].x) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

void mergey(int lo, int mi, int hi, node* a)
{
    node* A = a + lo;
    int lb = mi - lo;
    node* B = new node[lb];
    node* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    node* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0].y < C[0].y) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

void mergeSort(int lo, int hi, node* A, int sign)
{
    if(sign == 1) {
        if(hi - lo < 2) return;
        int mi = (lo + hi) / 2;
        mergeSort(lo, mi, A, sign); mergeSort(mi, hi, A, sign);
        mergex(lo, mi, hi, A);
    } else {
        if(hi - lo < 2) return;
        int mi = (lo + hi) / 2;
        mergeSort(lo, mi, A, sign); mergeSort(mi, hi, A, sign);
        mergey(lo, mi, hi, A);
    }
}

const int MAXN = 5e4 + 233, mo = 1e5 + 7;
node dt[MAXN];
int dp[MAXN][11][2], up[11][MAXN << 2], down[11][MAXN << 2];

int n, k;

void modify(int rt, int l, int r, int dir, int k, int pos, int v) {
    if(l == r) {
        if(dir == 0) up[k][rt] = v;
        else down[k][rt] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) modify(rt << 1, l, mid, dir, k, pos, v);
    else modify(rt << 1 | 1, mid + 1, r, dir, k, pos, v);
    if(dir == 0) up[k][rt] = (up[k][rt << 1] + up[k][rt << 1 | 1]) % mo;
    else down[k][rt] = (down[k][rt << 1] + down[k][rt << 1 | 1]) % mo;
}

int query(int rt, int l, int r, int s, int t, int dir, int k) {
    if(s > t) return 0;
    if(s <= l && r <= t) {
        if(dir == 0) return up[k][rt];
        else return down[k][rt];
    }
    int mid = (l + r) >> 1;
    if(t <= mid) return query(rt << 1, l, mid, s, t, dir, k) % mo;
    else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t, dir, k) % mo;
    else return (query(rt << 1, l, mid, s, t, dir, k) + query(rt << 1 | 1, mid + 1, r, s, t, dir, k)) % mo;
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1;i <= n;++ i) {
        scanf("%d%d", &(dt[i].x), &(dt[i].y));
    }
    mergeSort(1, n + 1, dt, 2);
    for(int i = 1;i <= n;++ i) 
        dt[i].y = i;
    mergeSort(1, n + 1, dt, 1);
    for(int i = 1;i <= n;++ i) {
        modify(1, 1, n, 0, 0, dt[i].y, 1);
        modify(1, 1, n, 1, 0, dt[i].y, 1);
        for(int j = 1;j <= k;++ j) {
            /*for(int m = 1;m < i;++ m) {
                if(dt[m].y < dt[i].y) {
                    dp[i][j][0] += dp[m][j][0];
                    dp[i][j][0] %= mo;
                    dp[i][j][0] += dp[m][j - 1][1];
                    dp[i][j][0] %= mo;
                } else {
                    dp[i][j][1] += dp[m][j][1];
                    dp[i][j][1] %= mo;
                    dp[i][j][1] += dp[m][j - 1][0];
                    dp[i][j][1] %= mo;
                }
            }*/
            dp[i][j][0] = (query(1, 1, n, dt[i].y + 1, n, 0, j) + query(1, 1, n, dt[i].y + 1, n, 1, j - 1)) % mo;
            dp[i][j][1] = (query(1, 1, n, 1, dt[i].y - 1, 1, j) + query(1, 1, n, 1, dt[i].y - 1, 0, j - 1)) % mo;
            modify(1, 1, n, 0, j, dt[i].y, dp[i][j][0]);
            modify(1, 1, n, 1, j, dt[i].y, dp[i][j][1]);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;++ i) {
        ans += dp[i][k][0];
        ans %= mo;
        ans += dp[i][k][1];
        ans %= mo;
    }
    printf("%d\n", ans);
}

victrid's solution

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
//TLE... It's segtree...
struct point {
    int x;
    int y;
    bool operator<=(point& other) {
        return x <= other.x;
    }
};

struct p_y : public point {
    bool operator<=(p_y& other) {
        return y <= other.y;
    }
};

template <typename T>
T* MergeSort(T* list, int listSize) {
    //<=
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0] <= list[1]) {
            return list;
        }
        T temp  = list[0];
        list[0] = list[1];
        list[1] = temp;
        return list;
    }
    T* tmplist = new T[listSize];
    T* llst    = MergeSort(list, listSize / 2);
    T* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    memcpy(list, tmplist, listSize * sizeof(T));
    delete[] tmplist;
    return list;
}
//......
point lst[50001];
long long dp[50001][11][2]   = {};
long long seq[200005][11][2] = {};

struct set {
    int l;
    int r;
    int current;
    set left() {
        return set{l, (l + r) >> 1, current << 1};
    }
    set right() {
        return set{((l + r) >> 1) + 1, r, current << 1 | 1};
    }
    bool isleaf() { return !(r - l); }
};
long long query(int l, int r, int d, int j, set s) {
    if (l > r)
        return 0;
    if (l <= s.l && s.r <= r) {
        return seq[s.current][j][d];
    }
    int mid      = (s.l + s.r) >> 1;
    long long q1 = 0, q2 = 0;
    if (l <= mid) {
        q1 = query(l, r, d, j, s.left());
    }
    if (r > mid) {
        q2 = query(l, r, d, j, s.right());
    }
    return q1 + q2;
}
void update(int l, int d, int j, long long chg, set s) {
    if (l < s.l || s.r < l) {
        return;
    }
    if (!s.isleaf()) {
        int mid = (s.l + s.r) >> 1;
        if (l <= mid) {
            update(l, d, j, chg, s.left());
        } else {
            update(l, d, j, chg, s.right());
        }
    }
    seq[s.current][j][d] += chg;
    seq[s.current][j][d] %= 100007;
    return;
}

int main() {
    int n, k, x, y;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        lst[i].x = x;
        lst[i].y = y;
    }
    //squeeze to continuous
    MergeSort((p_y*)(lst + 1), n);
    for (int i = 1; i <= n; i++) {
        lst[i].y = i;
    }

    MergeSort((lst + 1), n);
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0][0] = 1;
        dp[i][0][1] = 1;
        update(lst[i].y, 1, 0, 1, set{1, n, 1});
        update(lst[i].y, 0, 0, 1, set{1, n, 1});
        for (int j = 1; j <= k; j++) {
            dp[i][j][0] += query(1, lst[i].y - 1, 0, j, set{1, n, 1}) + query(1, lst[i].y - 1, 1, j - 1, set{1, n, 1});
            // ! direction revert
            dp[i][j][1] += query(lst[i].y + 1, n, 1, j, set{1, n, 1}) + query(lst[i].y + 1, n, 0, j - 1, set{1, n, 1});
            dp[i][j][0] %= 100007;
            dp[i][j][1] %= 100007;
            update(lst[i].y, 0, j, dp[i][j][0], set{1, n, 1});
            update(lst[i].y, 1, j, dp[i][j][1], set{1, n, 1});
            if (j == k) {
                total += dp[i][k][0] + dp[i][k][1];
                total %= 100007;
            }
        }
    }
    printf("%lld", total);
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
const int M=100007;
int ftree[262144][11],gtree[262144][11],df[11],dg[11],totalf[11],totalg[11],n,x[100001],y[100001],lastf,lastg,curf,curg,k;
inline int lowbit(int x) {
    return x&-x;
}
int query(int t[262144][11],int x,int k){
    int sum=0;
    while (x>0){
        sum=(sum+t[x][k])%M;
        x-=lowbit(x);
    }
    return sum;
}
void update(int t[262144][11],int x,int k,int d){
    while (x<=100000){
        t[x][k]=(t[x][k]+d)%M;
        x+=lowbit(x);
    }
}
void qsort(int l,int r){
    if (l+1>=r) return;
    int i=l,j=r-1,key=x[l],keyy=y[l];
    while (i<j){
        while (i<j&&x[j]>=key) --j;
        if (i<j){
            x[i]=x[j];
            y[i]=y[j];
            ++i;
        }
        while (i<j&&x[i]<=key) ++i;
        if (i<j){
            x[j]=x[i];
            y[j]=y[i];
            --j;
        }
    }
    x[i]=key;
    y[i]=keyy;
    qsort(l,i);
    qsort(i+1,r);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for (int i=0;i<n;++i)
        cin >> x[i] >> y[i];
    qsort(0,n);
    for (int i=0;i<n;++i) {
        lastf=query(ftree,y[i]-1,0);
        lastg=query(gtree,y[i]-1,0);
        for (int j=1;j<=k;++j)
        {
            curf=query(ftree,y[i]-1,j);
            curg=query(gtree,y[i]-1,j);
            df[j]=curf+lastg;
            dg[j]=totalg[j]-curg+totalf[j-1]-lastf;
            if (dg[j]<0) dg[j]+=M;//WTF???? Be Cautious!!!
            update(ftree,y[i],j,df[j]);
            update(gtree,y[i],j,dg[j]);
            lastf=curf;
            lastg=curg;
        }
        update(ftree,y[i],0,1);
        update(gtree,y[i],0,1);
        totalf[0]++;
        totalg[0]++;
        for (int j=1;j<=k;++j){
            totalf[j]=(totalf[j]+df[j])%M;
            totalg[j]=(totalg[j]+dg[j])%M;
        }
    }
    cout<<(totalf[k]+totalg[k])%M;
    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k;
pair<int, int> p[50005];
int vis[100005] = {0};
const int M = 100007;
int c[2][11][50005] = {0};
int f[2][11];
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= M ? x + y - M: x + y);
}
void add(int v, int k, int *cc){
    while (k <= n)
        cc[k] = modadd(cc[k], v), k += lowbit(k);
}
int query(int r, int *cc)   {
    int res = 0;
    while (r > 0)
        res = modadd(res, cc[r]), r -= lowbit(r);
    return res;
}
void init(){
    n = read(), k = read();
    for (int i = 1; i <= n; ++i)
        p[i].first = read(), p[i].second = read();
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)   
        vis[p[i].second] = i;
    int cur = 0;
    for (int i = 1; i <= 100000; ++i)
        if (vis[i]) p[vis[i]].second = ++cur;
}
void solve(){
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        int pos = p[i].second;
        // 求解
        for (int j = 1; j <= k; ++j)
            f[0][j] = modadd(query(pos - 1, c[0][j]), query(pos - 1, c[1][j - 1])), 
            f[1][j] = modadd(
                modadd(query(n, c[1][j]), M - query(pos, c[1][j])), 
                modadd(query(n, c[0][j - 1]), M - query(pos, c[0][j - 1]))
            );

        ans = modadd(ans, f[0][k]), ans = modadd(ans, f[1][k]);

        // 更新
        add(1, pos, c[0][0]), add(1, pos, c[1][0]);
        for (int j = 1; j <= k; ++j)
            add(f[0][j], pos, c[0][j]), add(f[1][j], pos, c[1][j]);
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}