bzoj 4515: [Sdoi2016]游戏

Description

Alice 和 Bob 在玩一个游戏。

游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。

有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，

若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。

他需要先从这条路径上选择一个点，再从那个点上选择一个数字。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

Input

第一行两个数字 n、m，表示树的点数和进行的操作数。

接下来 n−1 行，每行三个数字 u、v、w，表示树上有一条连接 u、v 的边，长度是 w。

接下来 m 行。每行第一个数字是 1 或 2。

若第一个数是 1，表示 Alice 进行操作，接下来四个数字 s、t、a、b。

若第一个数是 2，表示 Bob 进行操作，接下来四个数字 s、t。

Output

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字

Sample Input

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

Sample Output

123456789123456789
6
-106

HINT

n≤100000，m≤100000，∣a∣≤10000,0<=w，|b|<=10^9

Source

鸣谢Menci上传

SDOI惊现天天爱跑步的套路，首先a*dis+b，拆路径来讨论;

对于s-lca，变为a*(d[s]-d[i])+b,也就是-a*d[i]+a*d[s]+b;

对于lca-t，变为a*(d[s]+d[i]-2*d[lca]),也就是a*d[i]+a*(d[s]-2*d[lca])+b;

所以每个点的d[i]，就相当于是一个横坐标，然后对于这个点插入一个kx+b的直线;

因为树链剖分的log个区间中每个区间的d[i]是递增的;

那么就相当于对这一个区间插入了一条kx+b的直线;然后我们需要动态的维护每个节点的最小值；

那么因为横坐标都是整点，我们可以用线段树来维护这一个半平面交;

用一种比较特殊的标记永久化方法;标记在这个区间中的最小值在哪一条直线上;

然后区间插入直线的时候算出交点，然后分情况递归更改左右区间即可;具体做法看lych即可，太强了;

以下为蒯的：

不妨考虑标记永久化（这里只是一定程度上的永久化但还是要下传的）。

让线段树中的一个节点只对应一条直线，那么如果在这个区间加入一条直线怎么办呢？

要分类讨论，设新加入的f1(x)=k1x+b1，原来的f2(x)=k2x+b2，左端点为l，右端点为r，那么有：

1.f1(d[l])<f2(d[l])且f1(d[r])<f2(d[r])，对应一条直线在两个端点都比另一条小，那么显然在l~r中f1(x)处处比f2(x)小，直接把f2(x)替换为f1(x)；

2.同理若上式的两个符号都为>，那么f1(x)处处不如f2(x)优，不做更改。

3.k1<k2，那么由于不满足1.2，显然两条直线有交点，此时解不等式f1(x)<f2(x)得到x>(b1-b2)/(k2-k1)，那么判断(b1-b2)/(k2-k1)在左半区间还是右半区间递归下传即可；

4.k1>k2同理。

实际上这就是线段树维护半平面交的过程~~~~~

询问就简单多了，直接用标记永久化的线段树的方法更新即可。

// MADE BY QT666

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

#define lson x<<1

#define rson x<<1|1

#define int long long

using namespace std;

typedef long long ll;

const int N=400050;

const ll Inf=123456789123456789ll;

int head[N],to[N],nxt[N],v[N],d[N],deep[N],cnt,n,m,tot;

int size[N],dfn[N],id[N],tt,son[N],top[N],fa[N];

ll Min[N*4],lazy[N*4],k[N*4],b[N*4],ans;

void lnk(int x,int y,int z){

  to[++cnt]=y,nxt[cnt]=head[x],v[cnt]=z,head[x]=cnt;

  to[++cnt]=x,nxt[cnt]=head[y],v[cnt]=z,head[y]=cnt;

}

void dfs1(int x,int f){

  size[x]=1;deep[x]=deep[f]+1;

  for(int i=head[x];i;i=nxt[i]){

    int y=to[i];if(y==f) continue;

    d[y]=d[x]+v[i];dfs1(y,x);

    fa[y]=x;size[x]+=size[y];

    if(size[y]>size[son[x]]) son[x]=y;

  }

}

void dfs2(int x,int f){

  top[x]=f;dfn[x]=++tt;id[tt]=x;

  if(son[x]) dfs2(son[x],f);

  for(int i=head[x];i;i=nxt[i]){

    int y=to[i];if(y==fa[x]||y==son[x]) continue;

    dfs2(y,y);

  }

}

struct data{

  int l,r,fl;

}p[N];

int lca(int x,int y){

  tot=0;int fl=1;

  while(top[x]!=top[y]){

    if(deep[top[x]]<deep[top[y]]) swap(x,y),fl^=1;

    p[++tot]=(data){dfn[top[x]],dfn[x],fl};

    x=fa[top[x]];

  }

  if(deep[x]<deep[y]) swap(x,y),fl^=1;

  p[++tot]=(data){dfn[y],dfn[x],fl};

  return y;

}

void pushup(int x,int l,int r){

  if(l<r) Min[x]=min(Min[lson],Min[rson]);else Min[x]=Inf;

  if(lazy[x]){

    Min[x]=min(Min[x],min(k[x]*d[id[l]],k[x]*d[id[r]])+b[x]);

  }

}

void build(int x,int l,int r){

  if(l==r){Min[x]=Inf;return;}

  int mid=(l+r)>>1;

  build(lson,l,mid);build(rson,mid+1,r);

  pushup(x,l,r);

}

void update(int x,int l,int r,ll K,ll B){

  if(!lazy[x]){

    lazy[x]=1;k[x]=K,b[x]=B;pushup(x,l,r);return;

  }

  ll x1=d[id[l]]*K+B,y1=d[id[r]]*K+B,x2=d[id[l]]*k[x]+b[x],y2=d[id[r]]*k[x]+b[x];

  if(x1<=x2&&y1<=y2){

    k[x]=K,b[x]=B;pushup(x,l,r);return;

  }

  else if(x2<=x1&&y2<=y1){return;}

  else if(K<k[x]){

    int mid=(l+r)>>1;

    int fj=(B-b[x])/(k[x]-K)+1;

    if(fj<=d[id[mid]]){

      swap(k[x],K);swap(b[x],B);

      update(lson,l,mid,K,B);

    }

    else update(rson,mid+1,r,K,B);

    pushup(x,l,r);

  }

  else if(K>k[x]){

    int mid=(l+r)>>1;

    int fj=(b[x]-B-1)/(K-k[x]);

    if(fj>d[id[mid]]){

      swap(k[x],K),swap(b[x],B);

      update(rson,mid+1,r,K,B);

    }

    else update(lson,l,mid,K,B);

    pushup(x,l,r);

  }

}

void insert(int x,int l,int r,int xl,int xr,ll K,ll B){

  if(xl<=l&&r<=xr){update(x,l,r,K,B);return;}

  int mid=(l+r)>>1;

  if(xr<=mid) insert(lson,l,mid,xl,xr,K,B);

  else if(xl>mid) insert(rson,mid+1,r,xl,xr,K,B);

  else insert(lson,l,mid,xl,mid,K,B),insert(rson,mid+1,r,mid+1,xr,K,B);

  pushup(x,l,r);

}

void query(int x,int l,int r,int xl,int xr){

  if(xl<=l&&r<=xr) {ans=min(ans,Min[x]);return;}

  int mid=(l+r)>>1;

  if(lazy[x]) ans=min(ans,min(k[x]*d[id[xl]],k[x]*d[id[xr]])+b[x]);

  if(xr<=mid) query(lson,l,mid,xl,xr);

  else if(xl>mid) query(rson,mid+1,r,xl,xr);

  else query(lson,l,mid,xl,mid),query(rson,mid+1,r,mid+1,xr);

}

main(){

  scanf("%lld%lld",&n,&m);

  for(int i=1;i<n;i++){int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);lnk(x,y,z);}

  dfs1(1,0);dfs2(1,1);build(1,1,n);

  for(int i=1;i<=m;i++){

    int type;scanf("%lld",&type);

    if(type==1){

      int s,t,a,b;scanf("%lld%lld%lld%lld",&s,&t,&a,&b);

      int Lca=lca(s,t);

      ll k=a,b1=a*d[s]+b,b2=a*(d[s]-2*d[Lca])+b;

      for(int j=1;j<=tot;j++){

	if(p[j].fl==1) insert(1,1,n,p[j].l,p[j].r,-k,b1);

	else insert(1,1,n,p[j].l,p[j].r,k,b2);

      }

    }

    else{

      ans=Inf;int s,t;scanf("%lld%lld",&s,&t);

      int Lca=lca(s,t);

      for(int j=1;j<=tot;j++) query(1,1,n,p[j].l,p[j].r);

      printf("%lld\n",ans);

    }

  }

  return 0;

}

巴特西