[SDOI2016]游戏
description
一个长为\(n\)的数列，每个初始为123456789123456789。
操作：
0 s t a b:s到t的链上每个点x跟dist(s,x)*a+b取min。
1 s t:求s到t的链上的min。
solution
李超+树链剖分
关键是想好树链剖分的李超线段树下标维护的是什么(x的范围)。
显然一条链dfn从小到大，dis也是从小到大。即维护的是[dis[x],dis[y]]。但实际上为了下标区间的连续性，线段树节点表示的为[dfn[x],dfn[y]]
不过知道dfs序推出远节点的dis不难。
知道这个这道题就能做出来了。
code
点击查看代码
//wr1: 哭，我柿子推错了，我看我有20pt就排除了这种可能qaq……
//wr2: 某处提前算了F(id,l/r)但后面id会变，却直接拿去用。
#include
using namespace std;
typedef long long ll;
const int N=5e5+5;
const ll inf=123456789123456789ll;
struct _line{
ll k,b;
}L[N];
int n,m,ltot;
int nxt[N],to[N],head[N],ecnt,dfn[N],In[N];
ll dis[N],len[N];
void add_edge(int u,int v,int w) {nxt[++ecnt]=head[u];to[ecnt]=v;len[ecnt]=w;head[u]=ecnt;}
int top[N],Time,son[N],sz[N],dep[N],fa[N],ed[N];
void gt_son(int u) {
sz[u]=1;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];if(v==fa[u])continue;
fa[v]=u;dis[v]=dis[u]+len[i];dep[v]=dep[u]+1;
gt_son(v);
if(sz[v]>sz[son[u]]) {son[u]=v;}
sz[u]+=sz[v];
}
}
void gt_top(int u,int Tp) {
top[u]=Tp;
dfn[++Time]=u;In[u]=ed[Tp]=Time;
if(son[u])gt_top(son[u],Tp);
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];if(v==fa[u]||v==son[u])continue;
gt_top(v,v);
}
}
int bst[N<<2],ls[N<<2],rs[N<<2],nd,rt[N];
ll mn[N<<2];
struct node {int l,r;ll _l,_r;}T[N<<2];
ll F(int p,ll X) {return L[p].k*X+L[p].b;}
void Build(int &x,int l,int r) {
x=++nd;T[x]=(node){l,r,dis[dfn[l]],dis[dfn[r]]};mn[x]=inf;
if(l==r)return;
int mid=(l+r)>>1;
Build(ls[x],l,mid);Build(rs[x],mid+1,r);
}
void Update(int x,int l,int r,int id) {
if(T[x].l==T[x].r) {
ll _y=T[x]._l;
if(!bst[x]) {bst[x]=id;mn[x]=F(id,_y);return;}
ll w=F(id,_y);
if(F(bst[x],_y)>w) {bst[x]=id;mn[x]=w;}
return;
}
int mid=(T[x].l+T[x].r)>>1;
if(l<=T[x].l&&T[x].r<=r) {
ll _l(T[x]._l),_r(T[x]._r),_m(dis[dfn[mid]]);
if(!bst[x]) {bst[x]=id;mn[x]=min(mn[x],min(F(id,_l),F(id,_r)));return;}
if(F(bst[x],_m)>F(id,_m)) {swap(bst[x],id);}
if(F(bst[x],_l)>F(id,_l)) {Update(ls[x],l,r,id);}
if(F(bst[x],_r)>F(id,_r)) {Update(rs[x],l,r,id);}
mn[x]=min(min(F(bst[x],_l),F(bst[x],_r)),min(mn[ls[x]],mn[rs[x]]));
return;
}
if(l<=mid) Update(ls[x],l,r,id);
if(r>mid) Update(rs[x],l,r,id);
mn[x]=min(mn[x],min(mn[ls[x]],mn[rs[x]]));
}
ll kl,kr;
ll Ask(int x,int l,int r) {
// if(!x)printf("!");
if(l<=T[x].l&&T[x].r<=r){return mn[x];}
int mid=(T[x].l+T[x].r)>>1;
ll res=!bst[x]?inf:min(F(bst[x],max(T[x]._l,kl)),F(bst[x],min(T[x]._r,kr)));
if(l<=mid) {res=min(res,Ask(ls[x],l,r));}
if(r>mid) {res=min(res,Ask(rs[x],l,r));}
return res;
}
int Lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]dep[y])swap(x,y);
kl=dis[x],kr=dis[y];
res=min(res,Ask(rt[top[x]],In[x],In[y]));
return res;
}
void init_tree() {
gt_son(1);gt_top(1,1);
for(int l=1,r;l<=n;l=r+1) {
r=ed[dfn[l]];
Build(rt[dfn[l]],l,r);
}
}
void in_puts() {
scanf("%d%d",&n,&m);
for(int i=1;i