自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:48:03，当前版本为作者最后更新于2023-06-24 20:29:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

青蛙。毒瘤。赛时最高 12 分。

吐槽：前两个包数据好水。调试可以试试这些数据：

2 9 2 1
0 9
0 0 0

25

3 22 2 1
1 10 21
0 0 1

69

5 12 1 1
0 5 7 9 11
0 0 1

30

思路

我们首先介绍一下 30 分的做法。

考虑路径大概长啥样。

第一步是从出发点走到第一个充电站。

第二步是走到某一个端点。

第三步是走到另一个端点。

第四步是往回走一点点。也可能不往回走，这一步可能不存在。

详细分析一下：

第一步可能走到左边第一个，也可能走到右边第一个。第二步也有两个方向。所以是有四种情况的。

下文默认是向左走（与样例的方向一致）。下文称第一个充电站为出发点，称相邻两个充电站之间为段。

在出发点左侧的段：

要走过去再走回来，就顺带搞掉了 $2k$ 的长度。这 $2k$ 应当安排在中央。两边的就来回走。

在出发点右侧的段：

直接走过去，不回来，就顺带搞掉了 $k$ 的长度。这 $k$ 就安排在中央。两边来回走，跟上面一样。

往回走一点点时经过的段（这些段一定是所有段的一个后缀，且都在出发点右侧）：

考虑把这些段的贡献记做新贡献减原贡献，就能直接与上面的和相加了。

新贡献计算方法与出发点左侧的段完全一样。

往回走一点点的终点：

终点会在一段的中间。处理一下即可。

• e0 为走到端点并停在端点的代价，适用最右段。
• e1 为走到端点再走回来的代价，适用最左段。
• m0 为走完一段并走到另一端的代价，适用出发点右侧的段。
• m1 为走完一段并回到原端的代价，适用出发点左侧的段。
• m2 为走完一段并停在中间某处的代价，适用第四步的终点段。

code

#include<stdio.h>
#include<algorithm>
#include<vector>
#define N 250009
#define int long long
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,l,k,d,a[N];bool down[N];
inline int e0(int x)
{
	int ans=-x;
	for(int o=(x%k?x%k:k);x>0;x-=k)ans+=o<<1,o+=k;
	return ans;
}
inline int e1(int x)
{
	int ans=0;
	for(int o=(x%k?x%k:k);x>0;x-=k)ans+=o<<1,o+=k;
	return ans;
}
inline int m0(int x)
{
	int ans=x;x-=k;
	for(int o=(x%k?x%k:k),oo=k;x>0;x-=k)
		if(o<oo)ans+=o<<1,o+=k;
		else ans+=oo<<1,oo+=k;
	return ans;
}
inline int m1(int x)
{
	int ans=x<<1;x-=k+k;
	for(int o=(x%k?x%k:k),oo=k;x>0;x-=k)
		if(o<oo)ans+=o<<1,o+=k;
		else ans+=oo<<1,oo+=k;
	return ans;
}
inline int m2(int x)
{
	if(x<=k)return x;
	if(x<=k<<1)return x+x-k;
	int ans=x;x-=k+k;
	for(int o=(x%k?x%k:k),oo=k;x>0?1:(ans+=min(o,oo),0);x-=k)
		if(o<oo)ans+=o<<1,o+=k;
		else ans+=oo<<1,oo+=k;
	return ans;
}
inline int lft(const int&x)
{
	int ans=0;
	for(int i=x,j;;i=j)
	{
		for(j=i-1;j>=0&&down[j];--j);
		if(j>>63){ans+=e1(a[i]);break;}
		ans+=m1(a[i]-a[j]);
	}
	vector<int>b,c;
	for(int i=x,j;;i=j)
	{
		for(j=i+1;j<n&&down[j];++j);
		if(j==n)
		{
			ans+=e0(l-a[i]);
			b.emplace_back(e1(l-a[i])-e0(l-a[i]));c.emplace_back(0);
			break;
		}
		ans+=m0(a[j]-a[i]);
		b.emplace_back(m1(a[j]-a[i])-m0(a[j]-a[i]));
		c.emplace_back(m2(a[j]-a[i])-m0(a[j]-a[i]));
	}
	int bns=0;
	for(int i=b.size()-1,s=0;i>=0;--i)
		bns=min(bns,s+c[i]),s+=b[i];
	return ans+bns;
}
inline int rgt(const int&x)
{
	int ans=0;
	for(int i=x,j;;i=j)
	{
		for(j=i+1;j<n&&down[j];++j);
		if(j==n){ans+=e1(l-a[i]);break;}
		ans+=m1(a[j]-a[i]);
	}
	vector<int>b,c;
	for(int i=x,j;;i=j)
	{
		for(j=i-1;j>=0&&down[j];--j);
		if(j>>63)
		{
			ans+=e0(a[i]);
			b.emplace_back(e1(a[i])-e0(a[i]));c.emplace_back(0);
			break;
		}
		ans+=m0(a[i]-a[j]);
		b.emplace_back(m1(a[i]-a[j])-m0(a[i]-a[j]));
		c.emplace_back(m2(a[i]-a[j])-m0(a[i]-a[j]));
	}
	int bns=0;
	for(int i=b.size()-1,s=0;i>=0;--i)
		bns=min(bns,s+c[i]),s+=b[i];
	return ans+bns;
}
main()
{
	read(n);read(l);read(k);read(d);
	for(int i=0;i<n;read(a[i++]));
	for(int z,u,p;d--;)
	{
		read(z);read(u);read(p);
		for(int x;z--;read(x),down[--x]=0);
		for(int x;u--;read(x),down[--x]=1);
		z=1ll<<60;u=lower_bound(a,a+n,p)-a;
		for(;u<n&&down[u];++u);
		if(u<n)z=min(z,a[u]-p+min(lft(u),rgt(u)));
		for(--u;u>=0&&down[u];--u);
		if(u>=0)z=min(z,p-a[u]+min(lft(u),rgt(u)));
		printf("%lld\n",z);
	}
}

思路

上面那个代码是依托答辩。但是可以吊打（波兰的）国家队。

容易发现 e0、e1、m0、m1、m2 都是可以 $\mathcal O(1)$ 计算的。

容易发现统计到达反方向的端点之前的答案是直接加和的形式，而统计往回走一点点对答案的贡献差是后缀和最小值的形式。

直接上数据结构维护即可。可以使用线段树。时限很够平衡树也行，但是难写一点。封装一下会舒服很多。

code

#include<stdio.h>
#include<set>
#define N 250009
#define ll long long
#define lc ((i)<<1|1)
#define rc ((i)+1<<1)
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,l,k,q,a[N];set<int>qwq;
inline ll e1(int x){return(x%k+x)*(x/k+1ll);}
inline ll e0(int x){return e1(x)-x;}
inline ll m_(int x)
{
	ll l1=x%k?x%k:k,cnt1=(x-1)/k+1+1>>1,l2=k,cnt2=(x-1)/k+1>>1;
	return(l1+l1+(cnt1-1)*k)*cnt1+(l2+l2+(cnt2-1)*k)*cnt2;
}
inline ll m0(int x){return x<=k?x:m_(x-k)+x;}
inline ll m1(int x){return x<=k+k?x+x:m_(x-k-k)+x+x;}
inline ll m2(int x)
{
	if(x<=k)return x;
	if(x<=k<<1)return x+x-k;
	x-=k<<1;ll l1=x%k?x%k:k,cnt1=(x-1)/k+1+1>>1,l2=k,cnt2=(x-1)/k+1>>1;
	return(l1+l1+(cnt1-1)*k)*cnt1+(l2+l2+(cnt2-1)*k)*cnt2+(x+k+k)+
		min(l1+cnt1*k,l2+cnt2*k);
}
inline ll d(int x){return e1(x)-e0(x);}
struct _
{
	ll s0,s1,pfx,pfxmn,sfx,sfxmn;
	inline _ operator+(const _&kkk)const
	{
		return(_){s0+kkk.s0,s1+kkk.s1,pfx+kkk.pfx,min(pfxmn,pfx+kkk.pfxmn)
			,sfx+kkk.sfx,min(kkk.sfxmn,kkk.sfx+sfxmn)};
	}
}tre[524288];
inline _ g(const int&x)
	{ll u=m0(x),v=m1(x),w=m2(x);return(_){u,v,v-u,w-u,v-u,w-u};}
inline void upd(int i,int l,int r,int p,int x)
{
	if(l==r){tre[i]=g(x);return;}
	int mid=l+r>>1;
	if(p<=mid)upd(lc,l,mid,p,x);
	else upd(rc,mid+1,r,p,x);
	tre[i]=tre[lc]+tre[rc];
}
inline pair<_,_>operator+(const pair<_,_>&x,const _&y)
	{return{x.first,x.second+y};}
inline pair<_,_>operator+(const _&x,const pair<_,_>&y)
	{return{x+y.first,y.second};}
inline pair<_,_>qry(int i,int l,int r,int p)
{
	if(l==r)return{_(),tre[i]};
	int mid=l+r>>1;
	if(p<=mid)return qry(lc,l,mid,p)+tre[rc];
	else return tre[lc]+qry(rc,mid+1,r,p);
}
inline ll qry(const int&x)
{
	if(qwq.size()==1)return min(e1(x)+min(e0(l-x),e1(l-x)),
		e1(l-x)+min(e0(x),e1(x)));
	pair<_,_>tmp=qry(0,0,n-1,lower_bound(a,a+n,x)-a);
	_ lft=tmp.first,rgt=tmp.second;
	return min(e1(*qwq.begin())+e0(l-*--qwq.end())+lft.s1+rgt.s0+
		min(0ll,rgt.sfxmn+d(l-*--qwq.end())),
		e1(l-*--qwq.end())+e0(*qwq.begin())+rgt.s1+lft.s0+
		min(0ll,lft.pfxmn+d(*qwq.begin())));
}
main()
{
	read(n);read(l);read(k);read(q);
	for(int i=0;i<n;read(a[i]),qwq.emplace(a[i++]));
	for(int i=0;i<n-1;++i)upd(0,0,n-1,i,a[i+1]-a[i]);
	for(int z,u,p;q--;)
	{
		read(z);read(u);read(p);
		for(int x,pos;z--;qwq.emplace(x))
		{
			read(x);pos=--x;x=a[x];
			if(x<*qwq.begin()){upd(0,0,n-1,pos,*qwq.begin()-x);continue;}
			if(x>*--qwq.end())
			{
				upd(0,0,n-1,lower_bound(a,a+n,*--qwq.end())-a,
					x-*--qwq.end());continue;
			}
			set<int>::iterator y=qwq.lower_bound(x),z=y;--y;
			upd(0,0,n-1,lower_bound(a,a+n,*y)-a,x-*y);
			upd(0,0,n-1,pos,*z-x);
		}
		for(int x,pos;u--;qwq.erase(x))
		{
			read(x);pos=--x;x=a[x];
			set<int>::iterator y=qwq.lower_bound(x),z=y;++z;
			upd(0,0,n-1,pos,0);
			if(y==qwq.begin())continue;--y;
			if(z==qwq.end())upd(0,0,n-1,lower_bound(a,a+n,*y)-a,0);
			else upd(0,0,n-1,lower_bound(a,a+n,*y)-a,*z-*y);
		}
		ll ans=1ll<<60;set<int>::iterator it=qwq.lower_bound(p);
		if(it!=qwq.end())ans=min(ans,*it-p+qry(*it));
		if(it!=qwq.begin())--it,ans=min(ans,p-*it+qry(*it));
		printf("%lld\n",ans);
	}
}