新题么。略水。


就一个序列,如果起点单增的话只要终点单增就不会冲突。


然后最少单增子序列覆盖=最长不降子序。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


typedef long long dint;


#define _l (long long int)


const int maxn = 100009;


int n, m, a[maxn], t[maxn], s;

dint v[maxn], v0[maxn];


int btQry(int p) {

int s = 0;

for (; p; p -= (p & -p))

s = max(s, t[p]);

return s;

}


void btChg(int p, int v) {

for (; p <= n; p += (p & -p))

t[p] = max(t[p], v);

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


scanf("%d%d", &n, &m);

for (int i = 0; i < n; ++ i) {

int p, s;

scanf("%d%d", &p, &s);

v0[i] = p + _l s * m;

v[i] = v0[i];

}

sort(v, v + n);

memset(t, 0, sizeof(t));

for (int i = 0; i < n; ++ i) {

int a = n - (lower_bound(v, v + n, v0[i]) - v);

int f = btQry(a) + 1;

btChg(a, f);

}

printf("%d\n", btQry(n));

}