Peaks

• description
• solution
• code

description

在Bytemountains有N座山峰，每座山峰有他的高度h_i

有些山峰之間有雙向道路相連，共M條路徑，每條路徑有一個困難值，這個值越大表示越難走

現在有Q組詢問，每組詢問詢問從點v開始只經過困難值小于等于x的路徑所能到達的山峰中第k高的山峰，如果無解輸出-1。

Input

第一行三個數N，M，Q

第二行N個數，第i個數為h_i

接下來M行，每行3個數a b c，表示從a到b有一條困難值為c的雙向路徑

接下來Q行，每行三個數v x k，表示一組詢問

Output

對于每組詢問，輸出一個整數表示答案。

Sample Input

10 11 4 1 2 3 4 5 6 7 8 9 10 1 4 4 2 5 3 9 8 2 7 8 10 7 1 4 6 7 1 6 4 8 2 1 5 10 8 10 3 4 7 3 4 6 1 5 2 1 5 6 1 5 8 8 9 2

Sample Output

6 1 -1 8

Hint

$N<=10^5,M,Q<=5?10^5，h_i,c,x<=10^9$

solution

困難值小于等于x，又是這種限制題，很容易聯想到前幾天才寫的[NOI2018]歸程

套路的，要對邊權進行排序，（通常還會有一步離散化），然后建立主席樹，每個$i$版本的線段樹表示邊權$\le x_i$的所有邊存在的樹/圖

本題思想是一致的，但是實現不同

使用kruskal重構樹

重構后，對樹dfn編序

葉子節點就表示該節點的高度，非葉子節點則表示該點子樹內最大邊權

每次查詢的最大邊限制x，就可以從v開始倍增地在dfs樹上跳邊，直到跳到某個祖先節點存的值是最大的小于等于x的邊權，此時再往上跳邊權就超過了x的限制

所以v能到達的點就是這個祖先節點管轄的區間內的所有點

kruskal重構樹，深度越小的點代表的邊權越大；實現是從小往上逐漸構造出一棵MST

利用dfn序列的性質，一個點子樹內dfn序是一段連續區間，可以用線段樹維護

直接線段樹里面查即可

具體而言：對每個點都建立權值線段樹，對每個點的線段樹版本可持久化，查祖先管轄區間內的值就是其管轄區間右端點版本減去其管轄區間左端點的前一個版本

code

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define maxn 500005 int n, m, Q, cnt; vector < int > G[maxn]; struct edge { int u, v, w; } E[maxn]; struct node { int lson, rson, tot; } t[maxn * 30]; int St[maxn], Ed[maxn], fa[maxn], h[maxn], d[maxn], root[maxn], id[maxn], dfn[maxn]; int f[maxn][20];int find( int x ) { return x == fa[x] ? x : fa[x] = find( fa[x] ); }void dfs( int u, int p ) {dfn[St[u] = ++ cnt] = u, f[u][0] = p;for( int i = 1;i < 20;i ++ )f[u][i] = f[f[u][i - 1]][i - 1];for( auto v : G[u] ) dfs( v, u );Ed[u] = cnt; }void modify( int &now, int lst, int l, int r, int pos ) {t[now = ++ cnt] = t[lst];t[now].tot ++; if( l == r ) return;int mid = ( l + r ) >> 1;if( pos <= mid ) modify( t[now].lson, t[lst].lson, l, mid, pos );else modify( t[now].rson, t[lst].rson, mid + 1, r, pos ); }int query( int L, int R, int l, int r, int k ) {if( l == r ) return l;int x = t[t[R].lson].tot - t[t[L].lson].tot;int mid = ( l + r ) >> 1;if( k <= x ) return query( t[L].lson, t[R].lson, l, mid, k );else return query( t[L].rson, t[R].rson, mid + 1, r, k - x ); }int main() {scanf( "%d %d %d", &n, &m, &Q );for( int i = 1;i <= n;i ++ )scanf( "%d", &h[i] ), d[i] = h[i];sort( d + 1, d + n + 1 );int tot = unique( d + 1, d + n + 1 ) - d - 1;for( int i = 1;i <= n;i ++ )h[i] = lower_bound( d + 1, d + tot + 1, h[i] ) - d;for( int i = 1;i <= m;i ++ )scanf( "%d %d %d", &E[i].u, &E[i].v, &E[i].w );sort( E + 1, E + m + 1, []( edge x, edge y ) { return x.w < y.w; } );for( int i = 1;i <= n;i ++ ) id[i] = fa[i] = i;int N = n;for( int i = 1;i <= m;i ++ ) {int u = find( E[i].u ), v = find( E[i].v ), w = E[i].w;if( u ^ v ) {h[++ N] = w;G[N].push_back( id[u] );G[N].push_back( id[v] );id[fa[v] = u] = N;}}dfs( N, N );for( int i = 1;i <= N;i ++ )if( dfn[i] <= n ) modify( root[i], root[i - 1], 1, tot, h[dfn[i]] );else root[i] = root[i - 1];int lastans = -1, v, x, k;while( Q -- ) {scanf( "%d %d %d", &v, &x, &k );if( ~ lastans ) v ^= lastans, x ^= lastans, k ^= lastans;for( int i = 19;~ i;i -- )if( h[f[v][i]] <= x ) v = f[v][i];x = t[root[Ed[v]]].tot - t[root[St[v] - 1]].tot;if( x < k )x = -1;elsex = query( root[St[v] - 1], root[Ed[v]], 1, tot, x - k + 1 );printf( "%d\n", lastans = ( ~ x ) ? d[x] : -1 );}return 0; }

總結

以上是生活随笔為你收集整理的[ONTAK2010] Peaks加强版 （kruskal重构树+主席树+倍增）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。