Codeforces 960F 主席树 或 树状数组+map

F. Pathwalks

题意：
n 个点 m 条边的有向图，每条边有边权，有重边和自环。要找出满足条件的最长的路径：这条路径上的边是严格递增的，且路径上的边的标号(即题目给出的顺序) 也要是递增的。求出最长路径的长度。
tags：
假定 dp[u][w] 表示终点为 u 且上一条边 <= w 的最长的长度。我们按给定边的顺序加边，对于 u -> v ，我们就可以用 dp[u][w-1] 更新 dp[v][w] 。
但是dp[N][N] 存不下，也维护不了。
有两种方法：
1】树状数组 + map，骚操作...... 在查询的时候，只要查询 map 里面出现过的点就好了

// 960F
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 100005;

map< int , int > dp[N];
void Add(int v, int w, int y) {
    for( ; w<N; w+=w&-w) dp[v][w] = max(dp[v][w], y);
}
int query(int u, int w) {
    int ret = 0;
    for( ; w; w-=w&-w)
        if(dp[u].find(w)!=dp[u].end())
            ret = max(ret, dp[u][w]);
    return ret;
}

int main()
{
    int n, m, u, v, w;
    scanf("%d%d", &n, &m);
    int ans = 0;
    rep(i,1,m)
    {
        scanf("%d%d%d", &u, &v, &w);
        ++w;
        int tmp = query(u, w-1)+1;
        Add(v, w, tmp);
        ans = max(ans, tmp);
    }
    printf("%d
", ans);

    return 0;
}

2】直接主席树，对每个点建个线段树。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 200005, Maxn = 1e5+5;

#define  mid  (l+(r-l)/2)
struct Tree { int l, r, mx; } T[N*40];
int root[N], cnt;
int query(int l, int r, int k, int pos) {
    if(l==r) return T[k].mx;
    if(pos<=mid) return query(l, mid, T[k].l, pos);
    else  return max(T[T[k].l].mx, query(mid+1, r, T[k].r, pos));
}
void update(int l, int r, int &k, int x, int y) {
    if(k==0) k=++cnt;   T[k].mx=max(T[k].mx, y);
    if(l==r) return ;
    if(x<=mid) update(l, mid, T[k].l, x, y);
    else  update(mid+1, r, T[k].r, x, y);
}
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    int ans = 0;
    int u, v, w;
    rep(i,1,m)
    {
        scanf("%d%d%d", &u, &v, &w);
        w += 2;
        int tmp = query(1, Maxn, root[u], w-1) + 1;
        ans = max(ans, tmp);
        update(1, Maxn, root[v], w, tmp);
    }
    printf("%d
", ans);

    return 0;
}