【题目】

【题意】给定n个点m条边的有向图，可能不连通有重边有自环。每条边有编号 i 和边权 wi ，求最长的路径（可以经过重复节点）满足编号和边权都严格递增。n,m,wi<=10^5。

【算法】主席树+DP

【题解】这个和LIS十分类似，只要在考虑LIS的树状数组做法的前提下多考虑节点搭配问题，即f[i]=f[j]+1还需要e[j].v=e[i].u。

所以对每个节点建可持久化线段树，然后DP即可。（当然也可以用可持久化树状数组）

复杂度O(n log n)。

#include
      
       #include
       
        #define lowbit(x) (x&-x)using namespace std;const int maxn=100010;int n,m,f[maxn],rt[maxn],sz;struct tree{
    int l,r,mx;}t[maxn*20];void insert(int& k,int l,int r,int x,int y){    if(!k)k=++sz;t[k].mx=max(t[k].mx,y);    if(l==r)return;    int mid=(l+r)>>1;    if(x<=mid)insert(t[k].l,l,mid,x,y);    else insert(t[k].r,mid+1,r,x,y);}int query(int k,int l,int r,int x){    if(l==r)return t[k].mx;    int mid=(l+r)>>1;    if(x<=mid)return query(t[k].l,l,mid,x);    else return max(t[t[k].l].mx,query(t[k].r,mid+1,r,x));}int main(){    scanf("%d%d",&n,&m);    int ans=0;    for(int i=1;i<=m;i++){        int u,v,w;        scanf("%d%d%d",&u,&v,&w);        f[i]=query(rt[u],1,100000,w-1)+1;        insert(rt[v],1,100000,w,f[i]);        ans=max(ans,f[i]);    }    printf("%d",ans);    return 0;}