自动搬运

查看原文

来自洛谷，原作者为

	xie_lzh 『 vanitas vanitatum 』

搬运于2025-08-24 21:59:17，当前版本为作者最后更新于2024-10-27 20:32:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面十分简洁所以不复述题面。

我们发现，连续的一段高度相同的向日葵一定会一起增长，所以每次操作只会使相邻不同的向日葵变为相同的，而不会使连续相同的向日葵变为不同的。

基于上面这个性质，我们可以想到一种基于合并次数的做法。

我们考虑在现有情况下，相邻的两个连续段什么时候会合并。我们发现这个可以通过当前情况下两种方向照灯的长高情况直接二分出来。但是这个不一定是他们真正合并的时间，因为可能受到其他段长高后的影响。但是我们发现，这只会让合并时间提前，所以当前我们找到的合并时间最小的位置是不受影响的。

故我们可以每次找到合并时间最小的位置合并，记录下合并后的高度和时间。然后计算合并后与相邻段的合并时间。

容易想到将所有可能的合并丢进堆里，每次取出最小的。

但是这样又会有一个问题，如果相邻的两段的当前时间不一样，我该如何判断是否可以生长。

看起来不太好做，但是我们发现，一个位置的生长情况只会在合并时发生改变，而我们选择的是合并时间最小的位置，所以其他位置的生长情况不会发生改变。

所以我们可以直接求得其他位置在当前时间的高度，从而得知合并后的生长情况，然后我们可以直接重新计算相邻段之间的合并时间。

注意一下若取出的点的状态不是最新状态则不能更新。

如果无论怎样都不会出现合并就可以直接计算答案了。

复杂度 $\Theta(n\log n)$。

实现细节比较多。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define pii pair<int,int>
int sum[N][2];
int n,m,a[N],fa[N],L[N],R[N],tim[N],val[N],ans[N],op[N][2],siz[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
char c[N];
int getv(int x,int ntim)
{
	x=find(x);
	// int lx=(L[x]==1?0:find(L[x]-1));
	// int rx=(R[x]==n?0:find(R[x]+1));
	// op[0]={lx&&val[x]<val[lx]||(val[x]==val[lx]&&tim[x]>tim[lx])};
	// op[1]={rx&&val[x]<val[rx]||(val[x]==val[rx]&&tim[x]>tim[rx])};
	return val[x]+(op[x][0]?sum[ntim][0]-sum[tim[x]][0]:0)+(op[x][1]?sum[ntim][1]-sum[tim[x]][1]:0);
}
int sv(int x,int y)
{
	if(!x||!y) return m+5;
	x=find(x); y=find(y);
	int l=max(tim[x],tim[y]),r=m,mid;
	int xv=getv(x,l),yv=getv(y,l);
	if(xv==yv) return l;
	if(xv>yv) swap(x,y);
	// if(xv>yv||xv==yv&&tim[x]>tim[y]) swap(x,y);
	// if(val[x]>val[y]||(val[x]==val[y]&&tim[x]<tim[y])) swap(x,y);
	// if(a[x]>a[y]) swap(x,y);
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(getv(x,mid)>=getv(y,mid)) r=mid-1;
		else l=mid+1;
	}
	int pans=r+1;
	return r+1;
}
void merge(int x,int y)
{
	x=find(x); y=find(y);
	if(x==y) return ;
	fa[y]=x; siz[x]+=siz[y];
	// if(L[x]>L[y]) op[x][0]=op[y][0];
	// if(R[x]<R[y]) op[x][1]=op[y][1];
	R[x]=max(R[x],R[y]); L[x]=min(L[x],L[y]);
	op[x][0]=(L[x]!=1&&getv(find(L[x]-1),tim[x])>val[x]);
	op[x][1]=(R[x]!=n&&getv(find(R[x]+1),tim[x])>val[x]);
	// op[x][0]|=op[y][0]; op[x][1]|=op[y][1];
}
struct node
{
	int x,y,szx,szy,timx,timy,nxt;
};
bool operator <(node a,node b)
{
	return a.nxt>b.nxt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],val[i]=a[i];
	cin>>c+1;
	for(int i=1;i<=m;i++)
	{
		int p=(c[i]=='B');
		sum[i][p]=sum[i-1][p]+1;
		sum[i][p^1]=sum[i-1][p^1];
	}
	fill(siz+1,siz+1+n,1);
	iota(fa+1,fa+1+n,1);
	for(int i=1;i<=n;i++) L[i]=R[i]=i;
	for(int i=1;i<n;i++)
		if(a[i]==a[i+1]) merge(i,i+1);
	priority_queue<node> q;
	int ntim=0;
	for(int i=1;i<=n;i++)
		if(find(i)==i)
		{
			if(R[i]!=n) op[i][1]=(a[R[i]+1]>a[i]);
			if(L[i]!=1) op[i][0]=(a[L[i]-1]>a[i]);
		}
	for(int i=1;i<=n;i++)
		if(find(i)==i)
		{
			if(R[i]!=n) q.push(node{i,find(R[i]+1),siz[i],siz[find(R[i]+1)],0,0,sv(i,find(R[i]+1))});
			if(L[i]!=1) q.push(node{find(L[i]-1),i,siz[find(L[i]-1)],siz[i],0,0,sv(find(L[i]-1),i)});
		}
	while(!q.empty())
	{
		node u=q.top(); q.pop();
		int x=u.x,y=u.y,timx=u.timx,timy=u.timy,nxt=u.nxt,szx=u.szx,szy=u.szy;
		if(nxt>m) break;
		if(find(x)!=x||find(y)!=y) continue;
		// if(timx!=tim[x]||timy!=tim[y]) continue;
		if(siz[x]!=szx||siz[y]!=szy) continue;
		// if(a[x]<a[y])  swap(x,y);
		val[x]=getv(x,nxt); tim[x]=nxt;
		merge(x,y);
		int lx=(L[x]==1?0:find(L[x]-1));
		int rx=(R[x]==n?0:find(R[x]+1));
		if(lx) q.push({lx,x,siz[lx],siz[x],tim[lx],tim[x],sv(lx,x)});
		if(rx) q.push({rx,x,siz[rx],siz[x],tim[rx],tim[x],sv(x,rx)});
	}
	for(int i=1;i<=n;i++)
		if(find(i)==i) ans[i]=getv(i,m);
	for(int i=1;i<=n;i++) cout<<ans[find(i)]<<' '; cout<<'\n';
}