AT_joisc2017_c 手持ち花火 (Sparklers) 做题记录

有 $n$ 个人在一条数轴上，第 $i$ 个人位于 $X_i$。

每个人手中有一个烟花，每一个烟花可以燃烧 $T$ 秒。（可加强到每个人烟花燃烧时间不同）

第 $0$ 秒时，第 $k$ 个人的烟花开始燃烧。

人们可以在数轴上以相同的速度 $s$ 奔跑（即每秒奔跑 $s$ 个单位）。当两个人位于同一个位置，并且某一个人手中的烟花是点燃状态且另一个人手中的烟花未点燃，那么他们可以选择是否传火，即点燃另一个人手中的烟花。

求最小的非负整数 $s$ 使得所有人的烟花都可以被点燃。

$1\le n\le 10^5$，$0\le X_i,T\le 10^9$，$X_i\le X_{i+1}$。

对于刚开始只有 $k$ 点燃的一段时间，显然在 $k$ 遇到第一个人之前它的方向不变，且两边的人都往中间跑。不妨假设 $k$ 向右跑，那么可以看作是 $[1,k]$ 这些人不动，$[k+1,n]$ 这些人以 $2s$ 的速度向左跑；$k$ 向左跑同理。

而当 $k$ 和第一个人相遇后，显然不用急着传火。这个人会跟着 $k$，直到 $k$ 的烟花烧完的那一刻再传火。证明考虑如果这两人同向是显然的，异向的话假设这个人是 $k+1$，则相当于 $[1,k]$ 不动 $[k+1,n]$ 以 $2s$ 的速度向左。那么由于 $[1,k-1]$ 不动所以第 $k+1$ 个人早点去点燃它们还不如等到 $k$ 燃尽了再去。

所以有结论：

每个时刻，至多只有一个人手中的烟花是点燃的，且所有人一定一直在奔跑。

那么设 $a_i=X_{k-i+1}-X_{k-i},b_i=X_{k+i}-X_{k+i-1}$ 即左右两边的间隔序列，那么问题转化为打怪兽（双序列拓展版）：

有一个变量 $x$，刚开始 $x=2sT$。

每次可以选择 $a_1$ 或者 $b_1$，假设选择的数为 $w$，则要求 $x\ge w$，并且令 $x:=x-w+2sT$ 后在对应的序列中删去 $w$。

求最小的非负整数 $s$ 使得两个序列可以被删空。

那么二分，转化为判定问题。接下来有两种做法：

01 on Tree 做法

考虑打怪兽（每个怪兽贡献 $-a+b$，要求 $x>a$）的结论：

• 先打 $a\le b$ 的怪兽，按照 $a$ 从小到大打；
• 再打 $a>b$ 的怪兽，按照 $b$ 从大到小打；

两部分之间的顺序和第一部分很好理解，第二部分证明可以考虑倒着做。

这个相当于是树上打怪兽，要求要先打完祖先的怪兽才能打这个点上的。那么对于一个点 $u$，若按照这个顺序其排名比 $fa_u$ 靠前，则打完 $fa_u$ 一定马上就会打 $u$。所以可以将 $u$ 和 $fa_u$ 合并。

那么可以按照这个顺序维护一个最小堆，每次取出堆顶 $u$，如果 $u$ 是根则打它并将它删掉，否则合并它和它的父亲。

这样做单次 check 复杂度 $O(n\log n)$，总复杂度 $O(n\log^2n)$。

贪心做法

考虑不断对于两个序列找到最小的正收益（$\sum 2sT-a_i\ge0$）的前缀，如果当前不能获取任何一个正收益则死了，否则获取正收益并干掉这个前缀，直到两个序列都不存在正收益的前缀。

这样可以得知获取完正收益后变量 $x$ 的值 $val$。

接下来倒过来做，考虑找出剩下的怪兽至少要求 $x$ 是多少（$del$）才能打完。那么每次找到最小的正收益（$\sum a_i-2sT\ge 0$）的后缀，取两个序列的后缀中对 $del$ 改变最小的那个干掉。而由于不存在 $\sum 2sT-a_i\ge 0$ 的前缀，所以不断干掉正收益的后缀一定能把两个序列都删空。

最后判断是否 $val\ge del$ 即可。

这样做单次 check 复杂度 $O(n)$，总复杂度 $O(n\log n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=100005;
const ll inf=2e9,INF=9e18;

int n,k;
ll m;
ll pos[S];
int ka,kb;
ll a[S],b[S];

inline bool chk(ll x)
{
	ll ad=m*x*2;
	ll val=ad;
	int la=1,lb=1;
	{// first
		auto fndr=[&](ll a[],int l,int len){
			ll mxa=0;
			ll sma=0,smb=0;
			for(int i=l;i<=len;i++)
			{
				mxa=max(mxa,a[i]+sma-smb);
				sma+=a[i],smb+=ad;
				if(sma<=smb) return make_pair(mxa,i);
			}
			return make_pair(INF,-1);
		};
		auto va=fndr(a,la,ka),vb=fndr(b,lb,kb);
		while(1)
		{
			bool fl=false;
			if(val>=va.first)
			{
				while(la<=va.second) val-=a[la++],val+=ad;
				va=fndr(a,la,ka);
				fl=true;
			}
			if(val>=vb.first)
			{
				while(lb<=vb.second) val-=b[lb++],val+=ad;
				vb=fndr(b,lb,kb);
				fl=true;
			}
			if(!fl) break;
		}
		if(va.first!=INF||vb.first!=INF) return false;
	}
	// if(x==1)
	// {
		// printf("%d/%d %d/%d\n",la,ka,lb,kb);
		// printf("%lld\n",val);
	// }
	ll del=0;
	{// second
		int ra=ka,rb=kb;
		auto fndl=[&](ll a[],int r,int l){
			ll mxa=0;
			ll sma=0,smb=0;
			for(int i=r;i>=l;i--)
			{
				mxa=max(mxa,ad+sma-smb);
				sma+=ad,smb+=a[i];
				if(sma<=smb) return make_pair(mxa,i);
			}
			return make_pair(INF,-1);
		};
		auto va=fndl(a,ra,la),vb=fndl(b,rb,lb);
		while(ra>=la||rb>=lb)
		{
			if(vb.first>va.first)
			{
				del=max(del,va.first);
				while(ra>=va.second) del-=ad,del+=a[ra--];
				va=fndl(a,ra,la);
			}
			else
			{
				del=max(del,vb.first);
				while(rb>=vb.second) del-=ad,del+=b[rb--];
				vb=fndl(b,rb,lb);
			}
		}
	}
	return val>=del;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++) cin>>pos[i];
	{
		bool fl=true;
		for(int i=1;i<=n&&fl;i++) fl&=(pos[i]==pos[1]);
		if(fl) return cout<<"0\n",0;
	}
	for(int i=k-1;i>=1;i--) a[++ka]=pos[i+1]-pos[i];
	for(int i=k+1;i<=n;i++) b[++kb]=pos[i]-pos[i-1];
	ll lb=1,rb=inf,res=-1;
	while(lb<=rb)
	{
		ll mid=lb+rb>>1;
		if(chk(mid)) res=mid,rb=mid-1;
		else lb=mid+1;
	}
	cout<<res<<'\n';
	return 0;
}