专栏文章

题解：P10148 [Ynoi1999] M47升级型“钢铁阿诺”

jjerry1717
P10148题解参与者 9已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@minmuqbs
此快照首次捕获于
2025/12/02 04:59
3 个月前
此快照最后确认于
2025/12/02 04:59
3 个月前
查看原文

前言

本题相对卡常，而且评测机波动极大，建议先做弱化版，能过之后再来本题卡常。

题意

给定长为 nn 的序列，一开始值全为 00，操作是区间推平和查询区间和，询问是从第 LL 个操作执行第 RR 个操作中区间和的和，允许离线。

做法

首先考虑对于每个询问做扫描线，即从左到右将当前操作对操作 11 到操作 RR 的影响用一些东西表示出来。
因为这种东西感觉不存在低于根号的做法，所以先对序列分块，然后区间和就有散块和整块，于是拆成三种情况分别分析。
  • 所有修改对散块的贡献
对于这部分的贡献，我们考虑枚举区间和的散块，看这个值是什么时候被整块或散块覆盖的，然后把权值（也就是贡献）放到修改这个值的操作上。这样一定是对的，因为当这个地方有值的时候，对它产生影响的一定是最近的覆盖，更遥远的覆盖一定不如最近的那次覆盖。当需要计算贡献的时候，直接把大于等于 LL 的拿出来算和即可。
发现需要支持一个 O(nn)\mathcal O(n \sqrt n) 次单点修改，O(n)\mathcal O(n) 次查询后缀的和，使用树状数组就太不平衡了，直接用 O(1)−O(n)\mathcal O(1) - \mathcal O(\sqrt n) 分块可以完美平衡。
  • 整块修改对整块的贡献。
说明一下，整块修改被打散了不属于这一部分。
然后你会发现因为块的数量只有 O(n)\mathcal O(\sqrt n) 个，那和上一种情况就没有本质区别了，直接做就好。
  • 散块修改对整块的贡献
这里的散块修改包括被打散的整块修改，正常的散块修改和被别的散块修改或整块修改覆盖所以要删除的散块修改。
先考虑贡献的计算，对于新放上去的散块修改，你可以记录当前整块的求和次数为 sumisum_i，然后你需要放上去的权值为 aia_i，那么你需要维护 ∑i=LRai(sumR−sumi)\sum_{i=L}^{R} a_i (sum_R-sum_i)，发现可以拆成前后两部分贡献分别计算。
对于打散整块修改与覆盖别的散块覆盖，你考虑找到那些值被放上去的时间，然后在那个时间上加上你需要删除或增加的贡献就好了。
发现前两种散块修改数量都是 O(n)\mathcal O(n) 级别的，而且后面那种因为有颜色段均摊，也是 O(n)\mathcal O(n) 级别的。但是查询分了块，数量是 O(nn)\mathcal O(n \sqrt n) 的，于是使用两个 O(n)−O(1)\mathcal O(\sqrt n) - \mathcal O(1) 的分块，分别维护 sumi×aisum_i \times a_i 与 aia_i 和需要删除和增加的贡献即可。

代码

因为评测机波动，代码可能要多交几遍，反正挺玄学的。
CPP
struct ques{int l,r,id;}wen[500005]; //存操作 
struct caozuo{
	int l,r,opt,k;
}qu[500005];//存询问 
const int B=2765,S=564; //这个比较玄学 
int n,m,q,ti[500005],b[500005],tag[10001],L[10001],R[10001],bel[500005];
bool cmp(ques x,ques y){
	return x.r<y.r;
}
int a[500005],h[500005];
int L_[10001],R_[10001],bel_[500005];
long long f_[10001],qian_[500005],f_2[10001],qian_2[500005],ans[500005];
inline void add_q(int x,long long v){//这是 O1-Osqrt; 
	f_[bel_[x]]+=v;
	qian_[x]+=v;
}
inline long long query_q(int x){//这是 O1-Osqrt; 
	long long ans=0;
	for(int i=x;i<=R_[bel_[x]];i++)ans+=qian_[i];
	for(int i=bel_[x]+1;i<=bel_[m];i++)ans+=f_[i];
	return ans;
}
inline void add_g(int x,long long v,long long v2){//这是 O sqrt-O1; 
	for(int i=1;i<=bel_[x]-1;i++)f_[i]+=v;
	for(int i=L_[bel_[x]];i<=x;i++)qian_[i]+=v; 
	for(int i=1;i<=bel_[x]-1;i++)f_2[i]+=v2;
	for(int i=L_[bel_[x]];i<=x;i++)qian_2[i]+=v2;
}
int sum;//整块查询次数 
int Vis=0,Cov=0;
inline long long query_g(int x){//这是 O sqrt-O1; 
	return 1ll*(qian_[x]+f_[bel_[x]])*1ll*sum-1ll*(qian_2[x]+f_2[bel_[x]]);
}
inline void pushdown(int be){
	if(!tag[be])return;
	for(int i=L[be];i<=R[be];i++){
		ti[i]=tag[be];
		b[i]=qu[tag[be]].k;
	}
	tag[be]=0;
} //下放标记 
inline void modify(int l,int r,int t){
	a[0]=0;
	for(int i=l;i<=r;i++){
		if(ti[i]){
			if(!h[ti[i]])a[++a[0]]=ti[i];
			h[ti[i]]++;
		}
		ti[i]=t; //套着 颜色段均摊，不用怕时间 
	}
	for(int i=1;i<=a[0];i++){
		long long cnt=1ll*qu[a[i]].k*h[a[i]];
		h[a[i]]=0;
		add_g(a[i],-cnt,-1ll*cnt*sum); //聪明的 转化成前缀和加与单点查，较少麻烦 
	}
	if(t)add_g(t,1ll*qu[t].k*(r-l+1),1ll*sum*qu[t].k*(r-l+1));
	if(Vis&&Cov){
		add_g(Cov,1ll*Vis*(((R[bel[l]]-L[bel[r]]+1))-(r-l+1)),1ll*sum*Vis*((R[bel[l]]-L[bel[r]]+1)-(r-l+1)));
		for(int i=L[bel[l]];i<=l-1;i++)ti[i]=Cov; 
		for(int i=r+1;i<=R[bel[r]];i++)ti[i]=Cov; 
	}
	Vis=0; //一定要还原 
}
inline void work(){
	memset(ti,0,sizeof(ti));
	for(int i=1;i<=bel[n];i++){
		Vis=0,Cov=0;
		sum=0;
		int idx=1;
		memset(f_,0,sizeof(f_));
		memset(f_2,0,sizeof(f_2));
		memset(qian_,0,sizeof(qian_));
		memset(qian_2,0,sizeof(qian_2));
		for(int j=1;j<=m;j++){
			int X=bel[qu[j].l],Y=bel[qu[j].r];
			if(qu[j].opt==2){
				if(qu[j].l<L[i]&&R[i]<qu[j].r){
					sum++;
				}
			}else{
				if(qu[j].l<L[i]&&R[i]<qu[j].r){
					if(!Vis){
						modify(L[i],R[i],0); 
					}
					Vis=qu[j].k;Cov=j;
				}else if(L[i]<=qu[j].l&&qu[j].r<=R[i])modify(qu[j].l,qu[j].r,j);
				else if(i==X)modify(qu[j].l,R[i],j);
				else if(i==Y)modify(L[i],qu[j].r,j);
			}
			while(idx!=q+1&&wen[idx].r==j){
				ans[wen[idx].id]+=query_g(wen[idx].l);
				idx++;
			}
		}
	}
}//此处是 散--整贡献 
inline void update(int l,int r,int v,int t){
	if(bel[l]==bel[r]){
		pushdown(bel[l]);
		for(int i=l;i<=r;i++){b[i]=v;ti[i]=t;}
	}else{
		pushdown(bel[l]);pushdown(bel[r]);
		for(int i=l;i<=R[bel[l]];i++){b[i]=v;ti[i]=t;}
		for(int i=r;i>=L[bel[r]];i--){b[i]=v;ti[i]=t;}
		for(int i=bel[l]+1;i<=bel[r]-1;i++){tag[i]=t;}
	}
}
inline void query_push(int l,int r){
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++){
			if(tag[bel[i]])add_q(tag[bel[i]],qu[tag[bel[i]]].k);
			else if(b[i])add_q(ti[i],b[i]);
		}
	}else{
		for(int i=l;i<=R[bel[l]];i++){
			if(tag[bel[i]])add_q(tag[bel[i]],qu[tag[bel[i]]].k);
			else if(b[i])add_q(ti[i],b[i]);
		}
		for(int i=L[bel[r]];i<=r;i++){
			if(tag[bel[i]])add_q(tag[bel[i]],qu[tag[bel[i]]].k);
			else if(b[i])add_q(ti[i],b[i]);
		}
		for(int i=bel[l]+1;i<=bel[r]-1;i++){
			if(tag[i])add_q(tag[i],1ll*qu[tag[i]].k*(R[i]-L[i]+1));
		}
	}
}
signed main(){
	for(int i=1;i<=q;i++)wen[i].id=i;
	sort(wen+1,wen+1+q,cmp);
	int idx=1;
	for(int i=1;i<=m;i++){
		if(qu[i].opt==1)update(qu[i].l,qu[i].r,qu[i].k,i);
		else query_push(qu[i].l,qu[i].r);
		while(idx!=q+1&&wen[idx].r==i){
			ans[wen[idx].id]+=query_q(wen[idx].l);
			idx++;
		}
	}
	work();
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
}

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...