bzoj 4515: [Sdoi2016]游戏（树链剖分+线段树）

Description

Input

Output

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

Sample Input

Sample Output

HINT

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

Source

鸣谢Menci上传

题解：树链剖分+线段树

这道题省选的时候不会手写栈打的暴力貌似就得了10分，呜呜。。。

这道题首先需要树链剖分，然后s,t之间路径上的加点就变成了线段树对应的一些区域加上了一条ax+b的线段，因为最终我们只需要知道区间的最小值，所以我们没有必要记录每一个值，只需要记录每个点的最小值。我们可以在区间加线段的时候，先定位到一个完全被线段覆盖的区间，然后在这个区间中下放线段，其实就是超哥线段树。

具体怎么做呢？

a1表示该原来区间记录的线段的斜率，a2表示加入直线的斜率。

1.a1

2.a1>a2也用上面的方式，不在赘述。

3.a1==a2&&b2

那么如何统计答案呢？在做超哥线段树的时候，我们单点查询的时候将到达当前点路过的所有区间记录的线段算出当前的点的值来更新答案。但是我们现在需要区间查询最小值，怎么办呢？我们对于每个区间记录一个最小值，val[i]=min(val[i<<1],val[i<<1|1])这还不够，我们需要用当前区间记录的线段更新答案，因为函数是单调的，所以只考虑左右端点即可。

我们这样只考虑了当前区间的记录的答案以及从他下放下去的答案，所以我们在最后统计答案的时候，需要将路过的包涵区间内点的线段都用来计算答案，也就是min(calc(tr[now],dis[q[max(ll,l)]]),calc(tr[now],dis[q[min(rr,r)]])).

这样这道题的主体就完成了，我们如果直接用a*dis(s,r)+b这样每次dis(s,r)都会改变，也就是每个点的x值是不断变化的，这样肯定没法直接维护线段，所以需要将式子变形。

设k=lca(s,t)

我们考虑(s,k)这一条路，dis[s,x]=dis[s,1]-dis[x,1]

a*dis[s,x]+b=a*(dis[s,1]-dis[x,1])+b=-a*dis[x,1]+a*dis[s,1]+b

我们成功将式子变成了一条斜率为-a,截距为a*dis[s,1]+b 的直线，且之后加入的每一条直线的自变量都是该点到跟的距离。

(k,t)这条路，dis[s,x]=dis[s,1]+dis[x,1]-2*dis[k,1]

最终化简成a*dis[x,1]+b+a*(dis[s,1]-2*dis[k,1])

这道题就解决啦。

#include
#include
#include
#include
#include
#define N 100003
#define LL long long
using namespace std;
const LL p=123456789123456789LL;
int n,m,tot,next[N*2],point[N],v[N*2],tr[N*4],sz,cnt;
int belong[N],pos[N],deep[N],f[N][30],mi[30],size[N],son[N],q[N];
LL c[N*2],val[N*4],dis[N];
struct data{
	LL a,b;
}seg[N*2];
void add(int x,int y,LL z)
{
	tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
	tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z;
}
void dfs(int x,int fa)
{
	deep[x]=deep[fa]+1; size[x]=1;
	for (int i=1;i<=19;i++){
		if (deep[x]-mi[i]<0) break;
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for (int i=point[x];i;i=next[i])
	 if (v[i]!=fa){
	 	f[v[i]][0]=x; dis[v[i]]=dis[x]+c[i];
	 	dfs(v[i],x);
	 	size[x]+=size[v[i]];
	 	if(size[v[i]]>size[son[x]]) son[x]=v[i];
	 }
}
void dfs1(int x,int chain)
{
	belong[x]=chain; pos[x]=++sz; q[sz]=x;
	if (!son[x]) return ;
	dfs1(son[x],chain);
	for (int i=point[x];i;i=next[i])
	 if (v[i]!=son[x]&&v[i]!=f[x][0])
	  dfs1(v[i],v[i]);
}
int lca(int x,int y)
{
	if (deep[x]>i&1) x=f[x][i];
	if (x==y) return x;
	for (int i=19;i>=0;i--)
	 if (f[x][i]!=f[y][i])
	  x=f[x][i],y=f[y][i];
	return f[x][0];
}
bool pd(int x,int y,LL pos)
{
	return seg[x].a*pos+seg[x].bseg[tr[now]].a)
     if (pd(x,tr[now],dis[q[mid]]))
      qjadd(now<<1|1,mid+1,r,tr[now]),tr[now]=x;
     else qjadd(now<<1,l,mid,x);
    if (seg[x].a==seg[tr[now]].a&&seg[x].bmid) change(now<<1|1,mid+1,r,ll,rr,x);
	update(now,l,r);
}
void solve(int x,int fa,int v)
{
	while (belong[x]!=belong[fa]){
		change(1,1,n,pos[belong[x]],pos[x],v);
		x=f[belong[x]][0];
	}
	change(1,1,n,pos[fa],pos[x],v);
}
LL find(int now,int l,int r,int ll,int rr)
{
	if (ll<=l&&r<=rr) return val[now];
	int mid=(l+r)/2;
	LL ans=p;
	if (tr[now]) ans=min(ans,min(calc(tr[now],dis[q[max(ll,l)]]),calc(tr[now],dis[q[min(rr,r)]])));
	if (ll<=mid) ans=min(ans,find(now<<1,l,mid,ll,rr));
	if (rr>mid) ans=min(ans,find(now<<1|1,mid+1,r,ll,rr));
	return ans;
}
LL solve1(int x,int y)
{
	LL ans=p;
	while (belong[x]!=belong[y]){
		if (deep[belong[x]]deep[y]) swap(x,y);
	ans=min(ans,find(1,1,n,pos[x],pos[y]));
	return ans;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("my.out","w",stdout);
	scanf("%d%d",&n,&m);
	mi[0]=1;
	for (int i=1;i<=19;i++) mi[i]=mi[i-1]*2;
	for (int i=1;i