[CTSC2016]时空旅行
Regimes
·
·
题解
题意：在一棵树上，每个节点代表一个集合，一些元素存在这个集合之中，每个
节点上的集合，是由父亲的先复制下来，然后修改1个元素，成为一个新的集合。
每个元素有(x,y,z,c)四个值，其实可以发现(y,z)没用，那么，就是两个(x,c)
每次给出树上一个点，以及一个X，要求出这个节点所有元素的
min( ( X - x_i)^2+C_i )
容易想到的是，我们用线段树维护这棵树的dfs序。于是，每个元素就存在
一些区间之中。于是我们可以先找到每个元素存在的区间，然后将这个元素存入
线段树所对应的区间之中。
接着我们可以推柿子了（精通斜率优化或者凸包的可以忽略）
我们令
(X-x_i)^2+C_i=X^2-2Xx_i+x_i^2+C_i=k
那么
2Xx_i+k=X^2+x_i^2+C_i
我们可以把每个(x_i,X^2+x_i^2+C_i)看作是个决策点，而我们有一个斜率为
让$k$尽量的小，也就是到$y$轴的截距。于是我们可以发现，对于每个节点，只需
要维护出一个凸包，然后对于一个$X$，找到斜率第一个大于$2X$的线段，它前面
的点既是最优决策。
但是这样空间开销很大。
于是我们对于$x_i$，从小到大的插入到每一个区间之中，在所对应的线段树的区
间上维护一个凸包。对于询问也对于$X$从小到达的去询问，找到对应的一个点，
并在经过的区间之中，求出最右解并取$min$.
并附上人帅但常数大的代码：
```cpp
#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
*/
```