题解：P14271 ABC428F 加强版

由于赛时没做出弱化版，于是恶补分块后来挑战这道题。

我们观察到弱化版，有一个性质，就是说后面的区间一定会包含前面的区间，所以

3

操作你直接找到第一个包含目标点的区间就做完了。

但是这道题不满足这个性质，于是好像只剩下分块能用了。

考虑每

B

个点分一块，则一共会被分成

\lceil {n\over B} \rceil

块。

我们先考虑查询怎么做。

对于散块你可以直接暴力带上 tag 统计是否包含。

对于整块按如下方法整理。

如果所有区间向左端对齐，也就是打了 $1$ 操作的 tag，那么可以将区间按长度从小到大排序，然后就可以转化成弱化版的 $3$ 操作去二分了，所以需要维护一个块内所有区间长度排序后的数组。
如果所有区间向右端对齐，那么也可以转化成弱化版的 $3$ 操作，但是由于输入的区间是左闭右开的，所以要仔细处理细节。
如果区间没有 tag，那么考虑一个块的答案等于所有小于等于 $x$ 的 $l$ 的个数减去所有小于等于 $x$ 的 $r$ 的个数，于是还要维护所有 $l$ 和所有 $r$ 排序后的数组。

所以时间复杂度为

\mathcal{O}(qB+q{n\over B}\log B)

。

现在考虑如何修改。

对于整块可以直接覆盖原来标记，这是容易的。

对于散块可以先把散块的标记暴力下传，然后处理修改后再暴力维护

l,r

排序后的数组。

时间复杂度

\mathcal{O}(q{n\over B}+qB\log B)

。

我不太会算

B

的最优值，求助了一下外界力量算出大概在

\sqrt n

时最优。

由于数据或常数原因，我

B

大概取

100

左右最优。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,B=91;
int n,m,pl[N],pr[N],ct;
int ql[N],qr[N],id[N];
int tp[N],pos[N],len[N],fl[N],fr[N];
void turn(int x,int tp,int pos){
	int ln=pr[x]-pl[x];
	if(tp==-1){
		pl[x]=pos,pr[x]=pos+ln;
	}else{
		pl[x]=pos-ln,pr[x]=pos;
	}
}
void pushdown(int x){
	if(!tp[x]) return ;
	for(int i=ql[x];i<=qr[x];i++) turn(i,tp[x],pos[x]);
	tp[x]=pos[x]=0;
}
void cg(int x){
	for(int i=ql[x];i<=qr[x];i++) fl[i]=pl[i],fr[i]=pr[i];
	sort(fl+ql[x],fl+qr[x]+1);
	sort(fr+ql[x],fr+qr[x]+1);
}
void add(int l,int r,int top,int ps){
	if(id[l]==id[r]){
		pushdown(id[l]);
		for(int i=l;i<=r;i++) turn(i,top,ps);
		cg(id[l]);
		return;
	}
	for(int i=id[l]+1;i<id[r];i++) tp[i]=top,pos[i]=ps;
	if(l==ql[id[l]]) tp[id[l]]=top,pos[id[l]]=ps;
	else{
		pushdown(id[l]);
		for(int i=l;i<=qr[id[l]];i++) turn(i,top,ps);
		cg(id[l]);
	}
	if(r==qr[id[r]]) tp[id[r]]=top,pos[id[r]]=ps;
	else{
		pushdown(id[r]);
		for(int i=ql[id[r]];i<=r;i++) turn(i,top,ps);
		cg(id[r]);
	}
}
int find1(int x,int k){
	if(tp[x]==-1){
		if(k<pos[x]) return 0;
		k=k-pos[x]+1;
		int p=upper_bound(len+ql[x],len+qr[x]+1,k)-len;
		return qr[x]-p+1;
	}else{
		if(k>=pos[x]) return 0;
		k=pos[x]-k+1;
		int p=lower_bound(len+ql[x],len+qr[x]+1,k)-len;
		return qr[x]-p+1;
	}
}
int find2(int x,int k){
	int p=upper_bound(fl+ql[x],fl+qr[x]+1,k)-fl-ql[x];
	int q=upper_bound(fr+ql[x],fr+qr[x]+1,k)-fr-ql[x];
	return p-q;
}
int ask(int l,int r,int x){
	if(id[l]==id[r]){
		int ans=0;
		for(int i=l;i<=r;i++){
			if(!tp[id[l]]) ans+=(pl[i]<=x&&x<pr[i]);
			if(tp[id[l]]==-1) ans+=(pos[id[l]]<=x&&x<pos[id[l]]+pr[i]-pl[i]);
			if(tp[id[l]]==1) ans+=(pos[id[l]]-pr[i]+pl[i]<=x&&x<pos[id[l]]);
		}
		return ans;
	}
	int ans=0;
	for(int i=id[l]+1;i<id[r];i++){
		if(tp[i]) ans+=find1(i,x);
		else ans+=find2(i,x);
	}
	if(l==ql[id[l]]){
		if(tp[id[l]]) ans+=find1(id[l],x);
		else ans+=find2(id[l],x);
	}
	else{
		for(int i=l;i<=qr[id[l]];i++){
			if(!tp[id[l]]) ans+=(pl[i]<=x&&x<pr[i]);
			if(tp[id[l]]==-1) ans+=(pos[id[l]]<=x&&x<pos[id[l]]+pr[i]-pl[i]);
			if(tp[id[l]]==1) ans+=(pos[id[l]]-pr[i]+pl[i]<=x&&x<pos[id[l]]);
		}
	}
	if(r==qr[id[r]]){
		if(tp[id[r]]) ans+=find1(id[r],x);
		else ans+=find2(id[r],x);
	}
	else{
		for(int i=ql[id[r]];i<=r;i++){
			if(!tp[id[r]]) ans+=(pl[i]<=x&&x<pr[i]);
			if(tp[id[r]]==-1) ans+=(pos[id[r]]<=x&&x<pos[id[r]]+pr[i]-pl[i]);
			if(tp[id[r]]==1) ans+=(pos[id[r]]-pr[i]+pl[i]<=x&&x<pos[id[r]]);
		}
	}
	return ans;
}
int qry(int top,int x){
	if(!tp[id[x]]){
		if(top==-1) return pl[x];
		else return pr[x];
	}
	if(tp[id[x]]==-1){
		if(top==-1) return pos[id[x]];
		else return pos[id[x]]+pr[x]-pl[x];
	}else{
		if(top==-1) return pos[id[x]]-pr[x]+pl[x];
		else return pos[id[x]];
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>pl[i]>>pr[i];
		id[i]=(i-1)/B+1;
		len[i]=pr[i]-pl[i]+1;
	}
	ct=id[n];
	for(int i=1;i<=n;i++){
		if(!ql[id[i]]) ql[id[i]]=i;
		qr[id[i]]=i;
	}
	for(int i=1;i<=ct;i++){
		cg(i);
		sort(len+ql[i],len+qr[i]+1);
	}
	while(m--){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==1) add(l,r,-1,qry(-1,c));
		if(opt==2) add(l,r,1,qry(1,c));
		if(opt==3) cout<<ask(l,r,c)<<"\n";
	}
	return 0;
}

AI 使用说明

本题解使用 gpt-5 求出了

B

的理论最小值。

题解：P14271 ABC428F 加强版

文章操作

相关推荐

评论

题解：P14271 ABC428F 加强版