专栏文章

题解：P5386 [Cnoi2019] 数字游戏

nnksunhaolan
P5386题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip9qy1n
此快照首次捕获于
2025/12/03 08:28
3 个月前
此快照最后确认于
2025/12/03 08:28
3 个月前
查看原文
感谢@ljy05提供 nnlog⁡2(n)n\sqrt{n}\log_2(n) 思路并参与讨论（人太菜不能一个人切黑）。

正文

step1

对于每一个询问 l,r,x,yl,r,x,y 我们可以把 (l,r)(l,r) 这一段区间内符合 x≤πi≤yx \le \pi_i \le y 的看做 1，反之为0。
那么就有 n×qn\times q 做法，统计区间内每一段连续 1 长度为 lenlen，ans=ans+len×(len+1)2ans=ans+{{len\times(len+1)}\over{2}}，扫过去求解即可（貌似常数小可以卡过子任务一？）。
时间 O(nq)O(nq)。

step2

也就是 @ljy05 提出的思路。
一看区间查询、不修改、不强制在线，简单莫队启动！因为是双区间，我们要考虑莫队哪一个区间，但是我们发现如果莫队数组区间，无论是修改还是查询都不好搞的样子，于是考虑莫队值域区间。
当你开始莫队值域区间时，你就会发现豁然开朗。
因为 π\pi 是排列，所以在莫队移动区间时，映射修改原数组就很方便。具体修改就这样：我们把值为 ii 的数在 π\pi 中的位置记为 AiA_i。在移动区间时，如果加入 ii 就把标记数组 visvis 的 visAivis_{A_i} 设为 truetrue ，退出 ii 时就把 visAivis_{A_i} 设为 falsefalse。
那现在问题转化为，如何快速单点修改，区间查询。
很容易想到线段树，于是就有了一个 O(qnlog⁡2(n))O(q\sqrt {n}\log_2(n)) 的做法，具体维护的话就是每个树节点维护 llen,rlen,ansllen,rlen,ans 即左边、右边连续 1 长度与该区间的答案，在更新与查询时注意边界与整块都是 1 的情况即可。
时间 O(qnlog⁡2(n))O(q\sqrt{n}\log_2(n))。

step3

学过莫队的都知道 O(qnlog⁡2(n))O(q\sqrt{n}\log_2(n)) 有可能被卡甚至不是正确复杂度，所以我们要优化。而莫队的优化方式大多是通过牺牲询问时间来把修改时间降低（多半是降至 O(1)O(1)）。
因为莫队的修改次数为 O(qn)O(q\sqrt{n}) 而询问次数为 qq。而分块通常就是一个很好的选择。
如何维护呢？我这里提出一种只加入不删除的做法（我太懒了，直接把回滚套上去就不想想删除了）。对于每一个下标维护 L,R,visL,R,vis，对每一个块维护 llen,rlen,ansllen,rlen,ans。L,RL,R 指每一个位置在块中所在 1 区间的左边界、右边界，visvis 指该位置是否是 1。llen,rlen,ansllen,rlen,ans 与上文线段树中提到的差不多。
修改时看是否会与其他区间合并，如果可以就更新新区间的 L,RL,R 以及所在块的 ansans，如果新区间接触块的左区间或右区间，就更新块内的 llen,rlenllen,rlen。
统计答案时散块整块查就是了，注意块与块间 llen,rlenllen,rlen 衔接与整块都是 1 的情况即可。
时间 O(qn)O(q\sqrt{n})。

代码

CPP
#include<bits/stdc++.h>
#define pl pair<int,int>
#define ll long long
using namespace std;

const int N=2e5+5,M=450;
//k,L,R,vis
int n,m,s,t,k,A[N],id[N];
int L[N],R[N];
ll ans[N];
bool vis[N];
struct nnd {
	int l,lk,r,x,y,idx;
}q[N];
//ls,rs,ans
struct node {
	int l,ls,r,rs,len;
	ll ans;
}D[M];
struct mmb {
	int x,it,lb,rb,L,R,ls,rs;
	ll ans;
}c[N<<1];
inline bool pai(const nnd& x,const nnd& y){
	return (x.lk^y.lk)?(x.lk<y.lk):(x.r<y.r);
}
inline void change(const int& x,const bool& dis){
	vis[x]=1;
	const int it=id[x],l=D[it].l,r=D[it].r;
	const int lb=((x^l)&&vis[x-1])?(L[x-1]):(x);
	const int rb=((x^r)&&vis[x+1])?(R[x+1]):(x);
	if(dis)c[++k]={x,it,lb,rb,L[rb],R[lb],D[it].ls,D[it].rs,D[it].ans};
	D[it].ans-=(ll)(x-lb)*(x-lb+1)/2+(ll)(rb-x)*(rb-x+1)/2;
	R[lb]=rb,L[rb]=lb;
	D[it].ans+=(rb-lb+1)*(rb-lb+2)/2;
	if(lb==l)D[it].ls=rb-lb+1;
	if(rb==r)D[it].rs=rb-lb+1;
}
void cle(){
	k=0;
	for(int i=1;i<=t;i++)
		D[i].ans=D[i].ls=D[i].rs=0;
	for(int i=1;i<=n;i++)
		L[i]=R[i]=vis[i]=0;
}
void ret(){
	for(;k;k--){
		const mmb p=c[k];
		vis[p.x]=0;
		L[p.rb]=p.L;
		R[p.lb]=p.R;
		D[p.it].ls=p.ls;
		D[p.it].rs=p.rs;
		D[p.it].ans=p.ans;
	}
}
inline ll get_ans(const int& l,const int& r){
	const int st=id[l],ed=id[r];
	ll ans=0,sum=0;
	if(st==ed){
		for(int j=l;j<=r;j++){
			if(vis[j]){
				sum++;
				if(j==r||!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
			}
		}
	} else {
		for(int j=l;j<=D[st].r;j++){
			if(vis[j]){
				sum++;
				if(!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
			}
		}
		for(int j=st+1;j<ed;j++){
			const ll l=D[j].ls,r=D[j].rs;
			if(D[j].len==l)
				sum+=l;
			else {
				sum+=l;
				ans+=sum*(sum+1)/2;
				sum=r;
				ans+=D[j].ans-l*(l+1)/2-r*(r+1)/2;
			}
		}
		if(!vis[D[ed].l]){
			ans+=sum*(sum+1)/2;
			sum=0;
		}
		for(int j=D[ed].l;j<=r;j++){
			if(vis[j]){
				sum++;
				if(j==r||!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
			}
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>m;
	s=sqrt(n),t=(n-1)/s+1;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		A[x]=i,id[i]=(i-1)/s+1;
	}
	for(int i=1,l,r;i<=t;i++){
		l=(i-1)*s+1,r=min(i*s,n);
		D[i]=(node){l,0,r,0,r-l+1,0};
	}
	for(int i=1,l,r,x,y;i<=m;i++){
		cin>>x>>y>>l>>r;
		q[i]=(nnd){l,id[l],r,x,y,i};
	}
	sort(q+1,q+m+1,pai);	
	for(int i=1,r,R;i<=m;i++){
		r=q[i].lk*s;
		if(q[i].lk^q[i-1].lk)cle(),R=r;
		for(;R<q[i].r;)change(A[++R],0);
		for(int j=min(q[i].r,r);j>=q[i].l;)
			change(A[j--],1);
		ans[q[i].idx]=get_ans(q[i].x,q[i].y);
		ret();
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<"\n";
	return 0;
}
码风超抽估计也没入看得懂。

评论

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

正在加载评论...