ZJOI2018 胖

【题解】[ZJOI2018] 胖

题目描述：

Cedyks 是一个富有的男孩子。他住在著名的The Place（宫殿）中。

Cedyks 是一个努力的男孩子。他每天都做着不一样的题来锻炼他的The Salt（灵魂）。

这天，他打算在他的宫殿外围修筑一道城墙，城墙上有$n$ 座瞭望塔。你可以把城墙看做一条线段，瞭望塔是线段上的$n$ 个点，其中$1$ 和$n$ 分别为城墙的两个端点。其中第$i$ 座瞭望塔和第$i + 1$ 座瞭望塔的距离为$w_i$，他们之间的道路是双向的。

城墙很快就修建好了，现在Cedyks 开始计划修筑他的宫殿到城墙的道路。因为这题的题目名称，Cedyks 打算用他的宫殿到每一个瞭望塔的最短道路之和来衡量一个修建计划。

现在Cedyks 手上有$m$ 个设计方案，第$k$ 个设计方案会在宫殿和瞭望塔之间修建$T_k$ 条双向道路，第$i$ 条道路连接着瞭望塔$a_i$，长度为$l_i$。

计算到每一个瞭望塔的最短路之和是一个繁重的工程，本来Cedyks 想用广为流传的SPFA算法来求解，但是因为他的butter（缓冲区）实在是太小了，他只能转而用原始的贝尔福特曼算法来计算，算法的流程大概如下：

1. 定义宫殿是$0$ 号点，第$i$ 个瞭望塔是$i$ 号点，双向边$(u_i, v_i, l_i)$ 为一条连接$u_i$ 和$v_i$ 的双向道路。令$d$ 为距离数组，最开始$d_0 = 0, d_i = 10^{18}(i ∈ [1, n])$。

2. 令辅助数组$c = d$。依次对于每一条边$(ui, vi,wi)$ 进行增广，$c_{u_i} = min(c_{u_i} , d_{v_i} + w_i)$，$c_{v_i} = min(c_{v_i} , d_{u_i} + w_i)$。

3. 令$t$ 为$c$ 和$d$ 中不一样的位置个数，即令$S = \{i|c_i≠d_i\}$，则$t = |S|$。若$t = 0$，说明$d$就是最终的最短路，算法结束。否则令$d = c$，回到第二步。

因为需要计算的设计方案实在是太多了，所以Cedyks 雇佣了一些人来帮他进行计算。为了避免这些人用捏造出来的数据偷懒，他定义一个设计方案的校验值为在这个方案上运行贝尔福特曼算法每一次进入第三步$t$ 的和。他会让好几个雇佣来的人计算同样的设计方案，并比对每一个人给出的校验值。

你是Cedyks 雇佣来的苦力之一，聪明的你发现在这个情形下计算最短路的长度的和是一件非常简单的事情。但是寄人篱下不得不低头，你不得不再计算出每一个方案的校验值来交差。

数据范围

测试点	$n$	$m$	$K$	其他约定
7,8,9,10	$\le 2 \times 10^5$	$\le 2 \times 10^5$	$\le 2 \times 10^5$	无

对于 $100\%$ 的数据，保证每个设计方案 $a_i$ 两两不同且 $1\le a_i\le n$ 。
对于 $100\%$ 的数据，保证 $1\le w_i,l_i\le 10^9,1\le\sum K\le 2\times 10^5$ 。

题目分析：

我们不妨将通过额外的边连接的点称为特殊点。

可以发现任意一条到点 $x$ 可能的最短路径都必然是经过一条额外的边到达 $y$ 然后再直接从 $y$ 走到 $x$。
题目要我们求的其实就是当可走的边数逐个变多时，最短路的变化次数，可以考虑枚举每一个点，然后判断这个点的最短路变化了多少次。
具体来说就是按距离这个点的远近，从近到远地枚举每一个特殊点然后更新最短路，这样复杂度就是 $O(nk)$ 十分炸裂。
既然枚举点不行，就考虑枚举特殊点，然后判断这个特殊点可以对多少个点产生贡献。
可以发现的一点就是点 $i$ 可以更新的点一定是包含 $i$ 的一段区间 $[l,r]$，因为如果更新点 $x$ 不优，那么更新其更靠外的点一定也不优。
那么下面就是可以二分一个左右端点，问题转化为了判断点 $i$ 是否可以更新点 $j$。
如果点 $i$ 可以更新点 $j$，当且仅当距离 $j$ 不超过 $|i-j|$ 的点中，$i$ 是最优的点（严格最优），当然如果距离为 $|i-j|$ 的另一个点与 $i$ 一样优且距离更小的点更劣，那么我们默认在左边的点统计答案。
可以将距离拆一下，即；

• 若 $i < j$，则 $dis_{i,j} = suf_i - suf_j + l_i$
• 若 $i > j$，则 $dis_{i,j} = suf_j - suf_i + l_i$

所以对于第一种情况只需要维护 $suf_i + l_i$ 的最小值，第二种情况只需要维护 $-suf_i+l_i$ 的最小值，然后就可以判断了。
维护可以使用线段树。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int INF = 1e18+5;
int n,m,dis[N],len[N],p[N];
struct SGT{
	int mn[20 * N],ls[20 * N],rs[20 * N],tot,rt;
	void modify(int &now,int now_l,int now_r,int pos,int val){
		if(!now)	now = ++tot;
		if(now_l == now_r){
			mn[now] = min(mn[now],val);
			return;
		}
		int mid = (now_l + now_r)>>1;
		if(pos <= mid)	modify(ls[now],now_l,mid,pos,val);
		if(pos > mid)	modify(rs[now],mid+1,now_r,pos,val);
		mn[now] = min(mn[now],val);
	}
	int query(int now,int now_l,int now_r,int l,int r){
		if(!now)	return INF;
		if(l <= now_l && now_r <= r)	return mn[now];
		int mid = (now_l + now_r)>>1,ans = INF;
		if(l <= mid)	ans = min(ans,query(ls[now],now_l,mid,l,r));
		if(r > mid)		ans = min(ans,query(rs[now],mid+1,now_r,l,r));
		return ans;
	}
	void clean(int now){
		mn[now] = INF;
		if(ls[now])	clean(ls[now]),ls[now] = 0;
		if(rs[now])	clean(rs[now]),rs[now] = 0;
	}
}T1,T2;
bool chk(int x,int y){  //y 是否可以更新 x 
	int len = abs(y - x);
	if(y > x){
		int tmp = min(T1.query(T1.rt,1,n,x-len,x)-dis[x],dis[x]+T2.query(T2.rt,1,n,x,x+len-1));
		if(tmp <= dis[x]+T2.query(T2.rt,1,n,y,y))	return false;
		return true;
	}
	else{
		int tmp = min(T1.query(T1.rt,1,n,x-len+1,x)-dis[x],dis[x]+T2.query(T2.rt,1,n,x,x+len-1));
		if(tmp <= T1.query(T1.rt,1,n,y,y)-dis[x])	return false;
		tmp = dis[x]+T2.query(T2.rt,1,n,x+len,x+len);
		if(tmp < T1.query(T1.rt,1,n,y,y)-dis[x])	return false;
		return true;
	}
}
int get_l(int pos){
	int l = 1,r = pos,ans = pos;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(chk(mid,pos))	ans = mid,r = mid - 1;
		else	l = mid + 1;
	}
	return ans;
}
int get_r(int pos){
	int l = pos,r = n,ans = pos;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(chk(mid,pos))	ans = mid,l = mid + 1;
		else	r = mid - 1;
	}
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	memset(T1.mn,0x3f,sizeof(T1.mn));
	memset(T2.mn,0x3f,sizeof(T2.mn));
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<n; i++)	scanf("%lld",&dis[i]);
	for(int i=n-1; i>=1; i--)	dis[i] += dis[i+1];
	while(m--){
		int k;scanf("%lld",&k);
		for(int i=1; i<=k; i++){
			scanf("%lld%lld",&p[i],&len[i]);
			T1.modify(T1.rt,1,n,p[i],dis[p[i]]+len[i]);   //T1 就是在左边 
			T2.modify(T2.rt,1,n,p[i],len[i]-dis[p[i]]);   //T2 就是在右边 
		}
		int ans = 0;
		for(int i=1; i<=k; i++){
			int L = get_l(p[i]);
			int R = get_r(p[i]);
			ans += R - L + 1;
		}
		printf("%lld\n",ans);
		T1.clean(T1.rt);T1.rt = T1.tot = 0;
		T2.clean(T2.rt);T2.rt = T2.tot = 0;
	}
	return 0;
}