求的是跑了T分钟之后的情况，要求是每个跑道都没有被超越现象，问最少的跑道需求数量。
很明显的就是求一个反链的偏序问题，我们倒过来看，求最长不降序列，于是就可以用树状数组来进行查询了。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 1e5 + 7; int N; ll T, Lsan[maxN]; int trie[maxN] = {0}; void update(int x, int val) { while(x <= N) { trie[x] = max(trie[x], val); x += lowbit(x); } } int query(int x) { int ans = 0; while(x) { ans = max(trie[x], ans); x -= lowbit(x); } return ans; } struct node { ll a[2]; node(int _a=0, int _b=0):a{_a, _b} {} } t[maxN]; int main() { scanf("%d%lld", &N, &T); ll vi; for(int i=1; i<=N; i++) { scanf("%lld%lld", &t[i].a[0], &vi); t[i].a[1] = t[i].a[0] + vi * T; Lsan[i] = t[i].a[1]; } sort(Lsan + 1, Lsan + N + 1); int _UP = (int)(unique(Lsan + 1, Lsan + N + 1) - Lsan - 1); for(int i=1; i<=N; i++) t[i].a[1] = lower_bound(Lsan + 1, Lsan + _UP + 1, t[i].a[1]) - Lsan; int ans = 1; for(int i=N, tmp; i>=1; i--) { tmp = 1 + query((int)t[i].a[1]); ans = max(ans, tmp); update(t[i].a[1], tmp); } printf("%d\n", ans); return 0; }
