P4069 [SDOI2016]游戏
斯德哥尔摩
2018-07-23 19:34:32
[P4069 [SDOI2016]游戏](https://www.luogu.org/problemnew/show/P4069)
### 先讲一讲题外话
这$SDOI$最近几年怎么这么喜欢出毒瘤线段树？
比方说[P3703 [SDOI2017]树点涂色](https://www.luogu.org/problemnew/show/P3703)，比方说[P3707 [SDOI2017]相关分析](https://www.luogu.org/problemnew/show/P3707)。。。
我竟无言以对。。。
但是这题我竟然是$1A$！不敢相信。~~（虽然说看了题解。。。）~~
### 步入正题
这题不恶心，不毒瘤，但是用到了一种非常奇怪的线段树——**李超树**。
李超树，俗称超哥线段树，是国家队队爷李超发明出来专门解决这一类问题：
现有2种操作：
1. 在平面上插入一条直线$y=kx+b$
2. 求在$[l,r]$范围内直线上的点的纵坐标的最小值
对付这种问题，超哥线段树是这么解决的：
假设在$[l,r]$内原有的一条直线为$f(x)_ 1=k_1x+b_1$
在这个区间内加入的直线为$f(x)_ 2=k_2x+b_2$
1. 如果$f(l)_ 2>=f(l)_ 1,f(r)_ 2>=f(r)_ 1$，那么说明$f(x)_ 2$在这个区间内被$f(x)_ 1$吊打，那么不做任何操作。
2. 如果$f(l)_ 2<=f(l)_ 1,f(r)_ 2<=f(r)_ 1$，那么说明$f(x)_ 1$在这个区间内被$f(x)_ 2$吊打，那么直接替换即可。
3. 如果$f(l)_ 2<=f(l)_ 1,f(r)_ 2>=f(r)_ 1$或者$f(l)_ 2>=f(l)_ 1,f(r)_ 2<=f(r)_ 1$，说明两直线在这个区间内有交点，则取区间中点$mid$，判断两直线在区间$[l,mid]$中是否相交：是，则右区间$[mid+1,r]$改为在下方的直线，左区间递归求解；否，则左区间$[l,mid]$改为在下方的直线，右区间递归求解。
而递归求解最多涉及到$log_2n$个节点。
所以这样的复杂度上限是$O(log_2^2n)$。
然后，这题还需要用到标记永久化。
即我们不下传标记，在求区间最小值的时候，每次访问到一个和询问区间有交集的区间，把答案和这个区间所维护的线段取$min$。
再加上树上询问，就是套上一个树剖的复杂度$log_2n$，所以总的复杂度是$O(mlog_2^3n)$。
### 后记
所有的树上询问，如果树的形态不变，基本上可以套上一个树剖，然后转化成序列上的问题，之后就好做了。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) b[x].data
#define MUL(x) b[x].k
#define ADD(x) b[x].v
#define SIGN(x) b[x].flag
#define LSIDE(x) b[x].l
#define RSIDE(x) b[x].r
#define MAXN 100010
#define MAX (1LL<<62)
using namespace std;
int n,m,c=1,d=1;
int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],id[MAXN],pos[MAXN],top[MAXN];
long long dis[MAXN];
struct Graph{
int next,to,w;
}a[MAXN<<1];
struct Segment{
long long data,k,v;
bool flag;
int l,r;
}b[MAXN<<2];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void pushup(int rt){
DATA(rt)=min(DATA(rt),min(DATA(LSON),DATA(RSON)));
}
void buildtree(int l,int r,int rt){
int mid;
LSIDE(rt)=l;
RSIDE(rt)=r;
DATA(rt)=123456789123456789LL;
if(l==r)return;
mid=l+r>>1;
buildtree(l,mid,LSON);
buildtree(mid+1,r,RSON);
}
void change(long long k,long long v,int rt){
int mid;
if(!SIGN(rt)){
SIGN(rt)=true;
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=min(DATA(rt),min(dis[pos[LSIDE(rt)]]*k,dis[pos[RSIDE(rt)]]*k)+v);
return;
}
long long l1=dis[pos[LSIDE(rt)]]*MUL(rt)+ADD(rt),l2=dis[pos[LSIDE(rt)]]*k+v;
long long r1=dis[pos[RSIDE(rt)]]*MUL(rt)+ADD(rt),r2=dis[pos[RSIDE(rt)]]*k+v;
if(l2>=l1&&r2>=r1)return;
else if(l2<l1&&r2<r1){
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=min(DATA(rt),min(dis[pos[LSIDE(rt)]]*k,dis[pos[RSIDE(rt)]]*k)+v);
return;
}
mid=LSIDE(rt)+RSIDE(rt)>>1;
long long mid1=dis[pos[mid]]*MUL(rt)+ADD(rt),mid2=dis[pos[mid]]*k+v;
if(l2>=l1){
if(mid2>=mid1)change(k,v,RSON);
else{
change(MUL(rt),ADD(rt),LSON);
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=min(DATA(rt),min(dis[pos[LSIDE(rt)]]*k,dis[pos[RSIDE(rt)]]*k)+v);
}
}
else{
if(mid2>=mid1)change(k,v,LSON);
else{
change(MUL(rt),ADD(rt),RSON);
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=min(DATA(rt),min(dis[pos[LSIDE(rt)]]*k,dis[pos[RSIDE(rt)]]*k)+v);
}
}
pushup(rt);
}
void update(int l,int r,long long k,long long v,int rt){
int mid;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
change(k,v,rt);
return;
}
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)update(l,r,k,v,LSON);
if(mid<r)update(l,r,k,v,RSON);
pushup(rt);
}
long long query(int l,int r,int rt){
int mid;
long long ans=MAX;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return min(ans,DATA(rt));
mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans=min(ans,query(l,r,LSON));
if(mid<r)ans=min(ans,query(l,r,RSON));
if(SIGN(rt))ans=min(ans,min(dis[pos[max(LSIDE(rt),l)]]*MUL(rt),dis[pos[min(RSIDE(rt),r)]]*MUL(rt))+ADD(rt));
return ans;
}
inline void add(int u,int v,int w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
}
void dfs1(int rt){
son[rt]=0;size[rt]=1;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
dis[will]=dis[rt]+a[i].w;
fa[will]=rt;
dfs1(will);
size[rt]+=size[will];
if(size[will]>size[son[rt]])son[rt]=will;
}
}
}
void dfs2(int rt,int f){
id[rt]=d++;pos[id[rt]]=rt;top[rt]=f;
if(son[rt])dfs2(son[rt],f);
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(will!=fa[rt]&&will!=son[rt])
dfs2(will,will);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
void work_add(int x,int y,long long k,long long v){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
update(id[top[x]],id[x],k,v,1);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
update(id[x],id[y],k,v,1);
}
void work_min(int x,int y){
long long s=MAX;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
s=min(s,query(id[top[x]],id[x],1));
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
s=min(s,query(id[x],id[y],1));
printf("%lld\n",s);
return;
}
void work(){
int f,x,y;
long long k,v;
while(m--){
f=read();x=read();y=read();
if(f==1){
k=read();v=read();
int lca=LCA(x,y);
work_add(x,lca,-k,k*dis[x]+v);
work_add(y,lca,k,k*(dis[x]-dis[lca]*2)+v);
}
if(f==2)work_min(x,y);
}
}
void init(){
int u,v,w;
n=read();m=read();
for(int i=1;i<n;i++){
u=read();v=read();w=read();
add(u,v,w);
}
deep[1]=1;dis[1]=0;
dfs1(1);
dfs2(1,1);
buildtree(1,n,1);
}
int main(){
init();
work();
return 0;
}
```