[CF960F] Pathwalks – STL,权值线段树

给你一张 \(n\) 个点 \(m\) 条边的带权有向图，可能有重边和自环。边会按照顺序给出。让你求出一条经过边数最多的路径，使得路径上的边满足边权和出现的时间严格递增。路径可以重复经过同一个点。

Solution

按顺序处理所有边，对于每个点维护以这个点结尾，结尾边权为 \(?\) 时的最大长度

对于 \((u,v,w)\)，找出 \(u\) 的结尾边权为 \([0,w-1]\) 时的最大长度，拿去更新 \(v\) 的结尾边权为 \(w\) 时的最大长度即可

显然我们可以用动态开点权值线段树维护这一切

考虑到我们每次询问的都是 \([0,?]\) 的最大值，每次修改也只会让答案更大，所以 \([0,?]\) 的答案是关于 \(?\) 单调的

因此我们可以将权值线段树换成一个 std::map，表示结尾边权-最大长度的二元关系，并且我们只保留那些单调的关系

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
map<int,int> mp[N];
map<int,int>::iterator it,jt;
int n,m,u,v,w,ans;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>u>>v>>w;
        it=mp[u].lower_bound(w);
        int a=(it==mp[u].begin())?1:1+(--it)->second;
        it=mp[v].upper_bound(w);
        int c=(it==mp[v].begin())?0:(--it)->second;
        if(c<a) {
            ans=max(ans,mp[v][w]=max(mp[v][w],a));
            for(it=mp[v].upper_bound(w);!(it==mp[v].end()||(it->second>a));)
                mp[v].erase(it++);
        }
    }
    cout<<ans;
}