题意：
给定 n 个点 m条边的有向图，可能不连通，可能有重边，也可能会有自环。求最长的路径(可以经过重复节点)，使得这条路径的编号和权值都严格单调递增，其中编号指输入的顺序。路径的长度是指经过边的数量。
思路1：
要求编号也单调递增的话不妨按照输入顺序加边，之后只考虑让权值严格递增即可。
设d p [ i ] [ w ]表示以i为结尾并且最后一条边权为w的最长路径长度。那么该状态可以从所有以i为端点并且权值< w
现在要做的就是如何快速求出以j为起点的权值在[ 0 , w − 1 ]之间的长度最大值。
对每个节点都开一棵权值线段树，维护d p [ i ] [ 1 − 1 e 5 ]内最大值。单点更新，区间查询。
用动态开点来优化空间
由于权值可能为0,在输入的时候统一加1
代码1：
// Problem: CF960F Pathwalks // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF960F // Memory Limit: 250 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int>PII; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} #define read read() #define debug(x) cout<<#x<<":"<<x<<endl; const int maxn=2e5+7,inf=0x3f3f3f3f; int n,m; int dp[maxn],root[maxn],idx; struct node{ int l,r,w; }tr[maxn*40]; void update(int &p,int l,int r,int pos,int val){ if(!p) p=++idx; if(l==r){ tr[p].w=val;return ; } int mid=(l+r)/2; if(pos<=mid) update(tr[p].l,l,mid,pos,val); else update(tr[p].r,mid+1,r,pos,val); tr[p].w=max(tr[tr[p].l].w,tr[tr[p].r].w); } int query(int p,int l,int r,int ql,int qr){ if(p==0) return 0; if(ql<=l&&r<=qr) return tr[p].w; int mid=(l+r)/2,ans=0; if(ql<=mid) ans=max(ans,query(tr[p].l,l,mid,ql,qr)); if(qr>mid) ans=max(ans,query(tr[p].r,mid+1,r,ql,qr)); return ans; } int main(){ n=read,m=read; int ans=0; rep(i,1,m){ int u=read,v=read,w=read+1; dp[v]=query(root[u],1,100000,1,w-1)+1; ans=max(ans,dp[v]); update(root[v],1,100000,w,dp[v]); } write(ans); return 0; }
思路2：
由于只有单点修改和区间查询，可以用树状数组来代替线段树
- 用map代替数组，实施动态开点
代码2：
// Problem: CF960F Pathwalks // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF960F // Memory Limit: 250 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int>PII; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} #define read read() #define debug(x) cout<<#x<<":"<<x<<endl; const int maxn=2e5+7,inf=0x3f3f3f3f; int n,m; map<int,int>mp[maxn]; int dp[maxn]; int lowbit(int x){ return x&-x; } void update(int u,int pos,int w){ if(!pos) mp[u][pos]=max(mp[u][pos],w); else{ while(pos<maxn){ mp[u][pos]=max(mp[u][pos],w); pos+=lowbit(pos); } } } int query(int u,int pos){ int ans=mp[u][0]; while(pos>0){ ans=max(ans,mp[u][pos]); pos-=lowbit(pos); } return ans; } int main(){ n=read,m=read; int ans=0; rep(i,1,m){ int tmp=0; int u=read,v=read,w=read; tmp=query(u,w-1)+1; update(v,w,tmp); ans=max(ans,tmp); } write(ans); return 0; }
