笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「小技巧」 CF960F Pathwalks

posted on 2020-06-09 08:14:09 | under 题解 |

比较巧的一道题。

考虑这题本质其实是一个有向图上边的 LIS。于是就可以用类似 LIS 的贪心方式来做,只是转移的时候多了一个限制而已。

具体的,对每个 $x$ 维护一个 map (或者线段树),存入边权值为 $v$ 时的最长递增路径。考虑每次加进来一条边 $(u,v,w)$,答案就是从 $u$ 的 map 里找出最大的小于 $w$ 的值,根据单调性可知这一定是小于 $w$ 的那个最大值。然后暴力改就好了。不难知道这样做每条边至多被加一次、删一次,复杂度是 $O(m\log n)$ 。

#include <map>

#include <cstdio>

#include <algorithm>

using std :: map ;

using std :: lower_bound ;

#define en end
#define be begin

#define lbd lower_bound

const int N = 300010 ;

typedef long long ll ;

int ans ;
int res ;
int n, m ;

map <int, ll> lis[N] ;

int search(int x, int v){
    int ret = 0 ;
    auto p = lis[x].lbd(v) ;
    ret = (p == lis[x].be()) ? 0 : ((-- p) -> second) ; return ret ;
}

int main(){
    scanf("%d%d", &n, &m) ; int x, y, z ;
    for (int i = 1 ; i <= m ; ++ i){
        scanf("%d%d%d", &x, &y, &z) ;
        res = search(x, z) ; ++ res ;
        if (res > search(y, z)){
            auto p = lis[y].lbd(z) ; lis[y][z] = res ;
            for (auto q = p ; q != lis[y].en() ; ){
                if ((q -> second) > res) break ; q = lis[y].erase(q) ;
            }
        }
        ans = std :: max(ans, res) ;
    }
    printf("%d\n", ans) ; return 0 ;
}