自动搬运

查看原文

来自洛谷，原作者为

	Regimes 这个家伙AFO了，什么也没有

搬运于2025-08-24 22:10:33，当前版本为作者最后更新于2019-09-11 20:15:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：在一棵树上，每个节点代表一个集合，一些元素存在这个集合之中，每个

节点上的集合，是由父亲的先复制下来，然后修改1个元素，成为一个新的集合。

每个元素有$(x,y,z,c)$四个值，其实可以发现$(y,z)$没用，那么，就是两个$(x,c)$

每次给出树上一个点，以及一个$X$，要求出这个节点所有元素的

容易想到的是，我们用线段树维护这棵树的$dfs$序。于是，每个元素就存在

一些区间之中。于是我们可以先找到每个元素存在的区间，然后将这个元素存入

线段树所对应的区间之中。

接着我们可以推柿子了（精通斜率优化或者凸包的可以忽略）

我们令

那么

我们可以把每个$(x_i,X^2+x_i^2+C_i)$看作是个决策点，而我们有一个斜率为

$2X$的直线，只要我们经过这个点，意味着我们进行了一次决策，我们要做的就是

让$k$尽量的小，也就是到$y$轴的截距。于是我们可以发现，对于每个节点，只需

要维护出一个凸包，然后对于一个$X$，找到斜率第一个大于$2X$的线段，它前面

的点既是最优决策。

但是这样空间开销很大。

于是我们对于$x_i$，从小到大的插入到每一个区间之中，在所对应的线段树的区

间上维护一个凸包。对于询问也对于$X$从小到达的去询问，找到对应的一个点，

并在经过的区间之中，求出最右解并取$min$.

并附上人帅但常数大的代码：

#include<bits/stdc++.h>
using namespace std ;
#define N 500007
#define ls (x<<1)
#define rs (x<<1|1)
#define inf 1e17
#define LL long long
int n , m , tot , cnt , num ;
int nex[2*N] , fire[N] , to[2*N] ;
int L[4*N] , R[4*N] , a[N] , dfn[N] , To[N] ;
LL C[N] , Ans[N] , val[N] ;
struct node{
    LL x , val , opt ;
}RR[N] ;
bool operator < (node a , node b){ return a.val < b.val ;}
bool cmp(int a , int b){ // 求出一个排列，使得val递增
    return val[a] < val[b] ;
}
double kk(int x , int y){ // 求斜率
    return (double)( (double)val[x] * val[x] + (double)C[x] - 
    (double)val[y] * val[y] - (double)C[y] ) / (double)( (double)val[x] - (double)val[y] ) ;
}
void add(int u , int v){
    nex[++tot] = fire[u] ;
    fire[u] = tot ;
    to[tot] = v ;
    return ;
}
vector<int> AL[N] , AR[N] ;
vector<int> W[4*N] ;
void dfs(int x , int fr){ // 找到每一个包含的区间
    dfn[x] = ++num ;
    if( To[x] > 0 ) AL[To[x]].push_back( num ) ; // 从这个开始一定是个区间左端点
    if( To[x] < 0 ) AR[abs(To[x])].push_back( num - 1 ) ; // 从这个结束是个区间右端点
    for(int i = fire[x] ; i ; i = nex[i] ){
        int v = to[i] ;
        if( v == fr ) continue ;
        dfs( v , x ) ;
    }
    if( To[x] > 0 ) AR[To[x]].push_back( num ) ; //这个点结束则是个区间右端点
    if( To[x] < 0 ) AL[abs(To[x])].push_back( num + 1 ) ; // 这个后面的点一定是个区间左端点
}
void build(int x , int l , int r){
    L[x] = 0 , R[x] = -1 ; // 这是一个初始化，我就是这个地方调了比较久。
    if( l == r ) return  ;
    int mid = ( l + r ) >> 1 ;
    build( ls , l , mid ) ; build( rs , mid + 1 , r ) ;
}
void update(int x , int l , int r , int ll , int rr , int t ){
    if( ll == l && r == rr ){
        while( W[x].size() <= R[x] + 5 ) W[x].push_back( 0 ) ; // 保险一点。
        if( L[x] <= R[x] && val[W[x][R[x]]] == val[t] ){  // 可能存在x相等的。
            if( C[W[x][R[x]]] <= C[t] ) return ;
            R[x]-- ;
        }
        while( L[x] < R[x] && kk( W[x][R[x]] , t ) < kk( W[x][R[x]] , W[x][R[x] - 1] ) ) R[x]-- ;// 类似于斜率优化的维护凸包。
        W[x][R[x] + 1] = t ; R[x]++ ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    if( rr <= mid ) update( ls , l , mid , ll , rr , t ) ;
    else if( ll > mid ) update( rs , mid + 1 , r , ll , rr , t ) ;
    else update( ls , l , mid , ll , mid , t ) , update( rs , mid + 1 , r , mid + 1 , rr , t ) ;
}
LL query(int x , int l , int r , int pos , LL t , LL res ){
    LL res1 = inf ;
    while( L[x] < R[x] && kk( W[x][L[x]] , W[x][L[x] + 1] ) <= 2.0 * (double)t ) L[x]++ ; 
    //对于每一个区间都维护求一下。
    if( L[x] <= R[x] && W[x].size() > 0 ) res1 = 1ll * ( t - val[W[x][L[x]]] ) * ( t - val[W[x][L[x]]] ) + C[W[x][L[x]]] ;
    res1 = min( res , res1 ) ;
    if( l == r ) return res1 ;
    int mid = ( l + r ) >> 1 ;
    if( pos <= mid ) return query( ls , l , mid , pos , t , res1 ) ;
    else return query( rs , mid + 1 , r , pos , t , res1 ) ;
}
signed main()
{
    scanf("%d%d%lld" , &n , &m , &C[0] ) ;
    for(int i = 1 ; i <= n - 1 ; i++ ){
        int opt , u , y , z ;
        LL x ;
        scanf("%d" , &opt ) ;
        if( opt == 0 ){
            scanf("%d%lld" , &u , &x ) ;
            scanf("%lld%d%d%lld" , &val[x] , &y , &z , &C[x] ) ;
            To[i] = x ;
            add( u , i ) ; add( i , u ) ;
        }
        else{
            scanf("%d%lld" , &u , &x ) ;
            To[i] = -x ;
            add( u , i ) ; add( i , u ) ;
        }
    }
    dfs( 0 , 0 ) ; // dfs序，找出每个区间
    build( 1 , 1 , n ) ;
    for(int j = 1 ; j <= n ; j++ ) a[j] = j ;
    sort( a + 1 , a + n + 1 , cmp ) ; // 找出哪个val递增的排列
    update( 1 , 1 , n , 1 , n , 0 ) ; // 地球哪个要加上
    for(int k = 1 ; k <= n ; k++ ){
        int i = a[k] ;
        for(int j = 0 ; j < AL[i].size() ; j++ ){
            int L = AL[i][j] , R = AR[i][j] ;
            if( L <= R ) update( 1 , 1 , n , L , R , i ) ;
        }
    }
    for(int i = 1 ; i <= m ; i++ ){
        scanf("%lld%lld" , &RR[i].x , &RR[i].val ) ;
        RR[i].opt = i ;
    }
    sort( RR + 1 , RR + m + 1 ) ; // 询问按从小到大的顺序，可以使得每次操作可是直接取上一次凸包最前面的值。
    for(int i = 1 ; i <= m ; i++ ){
        Ans[RR[i].opt] = query( 1 , 1 , n , dfn[RR[i].x] , RR[i].val , inf ) ;
    }
    for(int i = 1 ; i <= m ; i++ ) printf("%lld\n" , Ans[i] ) ;
    return 0 ;
}

/*
4 4 2
0 0 1 10 2 3 7
0 1 2 8 1 6 2
1 1 1
1 4
2 8
2 6
3 8
*/