很不错的一道思维题。
Code:
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int maxn = 1000000 + 4; const int inf = 100000 + 4; int n, m; int root[maxn], maxv[maxn << 2],ch[maxn << 2][2], cnt; inline void get_max(int &a,int b) { if(b > a) a = b; } struct Segment_Tree { #define lson ch[o][0] #define rson ch[o][1] inline void update(int l,int r,int delta,int val,int &o) { if(!o) o = ++cnt; if(l == r) { get_max(maxv[o], delta); return; } int mid = (l + r) >> 1; if(val <= mid) update(l, mid, delta, val, ch[o][0]); else update(mid + 1, r, delta, val, ch[o][1]); get_max(maxv[o], max(maxv[lson], maxv[rson])); } inline int query(int l,int r,int L,int R,int o) { if(!o) return 0; if(l > r || r < L || l > R || L > R) return 0; if(l >= L && r <= R) return maxv[o]; int mid = (l + r) >> 1; return max(query(l, mid, L, R, lson), query(mid + 1, r, L, R, rson)); } }T; int main() { //freopen("input.in","r",stdin); scanf("%d%d",&n,&m); int ans = 0; for(int i = 1;i <= m; ++i) { int from, to, val; scanf("%d%d%d",&from, &to,&val); ++ val; int tmp = T.query(1, inf , 1, val - 1, root[from]); T.update(1, inf, tmp + 1, val, root[to]); get_max(ans, tmp + 1); } printf("%d",ans); return 0; }