p1081 开车旅行
嗯。。。非常好的一道倍增好题。。。。
你会发现对于每一个点，如果说是A开车，到达的点是固定的，是B
开车，到达的点也是固定的。并且他们只会去比他们要大的点。于是对于终点
只会有三种情况（当然是在可以走无限步时）
1.到了n点，接下来是A开车，旅程结束。
2.到了n点，接下来是B开车，旅程结束。
3.到了n-1点，接下来是A开车，旅程结束。
所以我们建出三棵树就行
我们把每个点进行拆点。1表示接下来B开，2表示接下来A开
那么必然就有树状的对应关系。
其他的留给倍增就行。。。
具体看代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
#define inf 0x7fffffff
#define Max(x,y) x>y?x:y
#define Min(x,y) x>y?y:x
int n , m , tot ;
int fa[N][33] , w[N][33] , w1[N][33] , To[N] , pi[N][3] , book[N] , bac[4*N] ;
int nex[4*N] , to[4*N] , fire[2*N] , dis[4*N] , from[4*N] ;
int L[N] , R[N] , s[N] , X[N] ;
struct node{
int H ;
int num ;
int w ;
}p[4 * N] ;
bool cmp(node x , node y){
return x.H < y.H ;
}
bool cmp2(node x , node y ){
if( x.w == y.w ) return x.H < y.H ;
return x.w < y.w ;
}
void add1(int u , int v , int fr ){
nex[++tot] = fire[u] ;
to[tot] = v ;
fire[u] = tot ;
dis[tot] = fr ;
from[tot] = u ;
}
void add(int u , int v , int fr ){
if( u == 0 || v == 0 ) return ;
if( abs( u - v ) == n ) return ;
add1( u , v , fr ) ; add1( v , u , fr ) ;
}
void build(){
//链表 ~ 链表
for(int i = 1 ; i <= n ; i++ ){
int now = To[i] ;
if( L[now] == 0 && R[now] ){ // 判断一定要啊。。被断送50p
add( pi[now][1] , pi[R[now]][2] , abs( p[R[now]].H - p[now].H ) ) ; // 在这里pi表的号都是排序后的标号
}
else{
if( L[now] && R[now] == 0 ){
add( pi[now][1] , pi[L[now]][2] , abs( p[L[now]].H - p[now].H ) ) ;
}
else{
if( abs( p[L[now]].H - p[now].H ) < abs( p[R[now]].H - p[now].H ) )
add( pi[now][1] , pi[L[now]][2] , abs( p[L[now]].H - p[now].H ) ) ;
else{
if( abs( p[L[now]].H - p[now].H ) == abs( p[R[now]].H - p[now].H ) ){
if( p[L[now]].H < p[R[now]].H ) add( pi[now][1] , pi[L[now]][2] , abs( p[L[now]].H - p[now].H ) ) ;
else add( pi[now][1] , pi[R[now]][2] , abs( p[R[now]].H - p[now].H ) ) ;
}
else{
add( pi[now][1] , pi[R[now]][2] , abs( p[R[now]].H - p[now].H ) ) ;
}
}
}
}
node k[521] ;
int cnt = 0 ;
if( L[now] >= 1 ) k[++cnt] = p[L[now]] , book[L[now]] = 1 ; // book 保险用的
if( L[L[now]] >= 1 && book[L[L[now]]] == 0 ) k[++cnt] = p[L[L[now]]] , book[L[L[now]]] = 1 ;
if( R[now] >= 1 && R[now] <= n && book[R[now]] == 0 ) k[++cnt] = p[R[now]] , book[R[now]] = 1 ;
if( R[R[now]] >= 1 && R[R[now]] <= n && book[R[R[now]]] == 0 ) k[++cnt] = p[R[R[now]]] , book[R[R[now]]] = 1 ;
for(int j = 1 ; j <= cnt ; j++ ) k[j].w = abs( p[now].H - k[j].H ) ;
sort( k + 1 , k + cnt + 1 , cmp2 ) ; // 懒得那么多判断，排一遍序
if( cnt >= 2 ) add( pi[now][2] , pi[k[2].num][1] , k[2].w ) ;
book[R[now]] = book[L[now]] = book[L[L[now]]] = book[R[R[now]]] = 0 ;
R[L[now]] = R[now] , L[R[now]] = L[now] ; // 左右儿子有变，改一下
}
}
void tree_build(int x , int bef , int fr ){
for(int i = fire[x] ; i ; i = nex[i] ){
int v = to[i] ;
if( v == fr ) continue ;
fa[v][0] = x ;
w[v][0] = dis[i] ; // 总共的 ， w - w1 就是 A 开的
if( bef == 1 )
w1[v][0] = dis[i] ; // 表示 这条路 是 B 开的，选上
tree_build( v , bef % 2 + 1 , x ) ;
}
}
signed main()
{
scanf("%d" , &n ) ;
for(int i = 1 ; i <= n ; i++ ) scanf("%d" , &p[i].H ) , p[i].w = i ; // p[i].w 表示原来时多少号，因为输入要按这个来
sort( p + 1 , p + n + 1 , cmp ) ;
for(int i = 1 ; i <= n ; i++ )
p[i].num = i , L[i] = i - 1 , R[i] = i + 1 , To[p[i].w] = i , bac[i] = p[i].w ;
// num表示现在的好，bac[i]其实可以忽略，直接用p[i].w
R[n] = 0 , L[1] = 0 ;
for(int i = 1 ; i <= 2 ; i++ )
for(int j = 1 ; j <= n ; j++ ) pi[j][i] = ( i - 1 ) * n + j ; //拆点
build() ;
tree_build( pi[To[n]][1] , 2 , 0 ) ; // n点 接下来 靠 B ， 上一次是 A
tree_build( pi[To[n]][2] , 1 , 0 ) ; // n点 接下来 靠 A ， 上一次是 B
tree_build( pi[To[n-1]][2] , 1 , 0 ) ; // n - 1 点 接下来 靠 A ，上一次 是 B
//建树
for(int j = 1 ; j <= 31 ; j++ ){ // 倍增预处理
for(int i = 1 ; i <= 2 * n ; i++ ){
fa[i][j] = fa[fa[i][j-1]][j-1] ;
w[i][j] = w[fa[i][j-1]][j-1] + w[i][j-1];
w1[i][j] = w1[fa[i][j-1]][j-1] + w1[i][j-1] ;
}
}
int x0 ;
scanf("%d" , &x0 ) ;
double Min = inf ;
int ans = 1 ;
for(int i = 1 ; i <= n ; i++ ){
int now = x0 , x1 = 0 , y1 = 0 ;
int b = pi[To[i]][2] ; // number的一个转化
for(int j = 31 ; j >= 0 ; j-- ){
if( w[b][j] <= now && fa[b][j] != 0 ){
x1 += w[b][j] ;
y1 += w1[b][j] ;
now -= w[b][j] ;
b = fa[b][j] ;
}
}
if( y1 == 0 ) continue ;
else{
if( Min > (double)( x1 - y1 ) / y1 ){
Min = (double)( x1 - y1 ) / y1 ;
ans = i ;
}
}
}
printf("%d\n" , ans ) ;
scanf("%d" , &m ) ;
for(int i = 1 ; i <= m ; i++ ){
scanf("%d%d" , &s[i] , &X[i] ) ;
int ans = 0 , res = 0 ;
s[i] = To[s[i]] + n ;
for(int j = 31 ; j >= 0 ; j-- ){
if( w[s[i]][j] <= X[i] && fa[s[i]][j] != 0 ){
ans += w1[s[i]][j] ;
res += w[s[i]][j] ;
X[i] -= w[s[i]][j] ;
s[i] = fa[s[i]][j] ;
}
}
printf("%d %d\n" , res - ans , ans ) ;
}
return 0 ;
}