# 11123: 【原1123】折线统计 Problem

### 题目描述

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

## 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
``````

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;
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;
}
}
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 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(){
for (int i = 1; i <= n; ++i)
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])),
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]))
);

// 更新