社区讨论

为何不能压行

P13978数列分块入门 3参与者 5已保存回复 17

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
17 条
当前快照
1 份
快照标识符
@miy8qh01
此快照首次捕获于
2025/12/09 15:10
3 个月前
此快照最后确认于
2025/12/11 22:46
3 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,block,num;
int a[200005],Belong[200005],Left[200005],Right[200005],add[200005],dirty[200005];
vector<int>Unordered_Array[200005];
vector<int>Ordered_Array[200005];
void init(){
	block=sqrt(N);
	num=N/block+(N%block!=0);
	for(int i=1;i<=N;i++)Belong[i]=(i-1)/block+1;
	for(int i=1;i<=num;i++)Left[i]=(i-1)*block+1;
	for(int i=1;i<=num;i++)Right[i]=i*block;
	Right[num]=N;
	for(int i=1;i<=N;i++)Unordered_Array[Belong[i]].push_back(a[i]);
}
void addv(int l,int r,int value){
	if(Belong[l]==Belong[r]){
		for(int i=l;i<=r;i++)Unordered_Array[Belong[l]][i-Left[Belong[l]]]+=value;
		dirty[Belong[l]]=0;
	}else{
		for(int i=l;i<=Right[Belong[l]];i++)Unordered_Array[Belong[l]][i-Left[Belong[l]]]+=value;
		for(int i=Belong[l]+1;i<=Belong[r]-1;i++)add[i]+=value;
		for(int i=Left[Belong[r]];i<=r;i++)Unordered_Array[Belong[r]][i-Left[Belong[r]]]+=value;
		dirty[Belong[l]]=0;dirty[Belong[r]]=0;
	}
}
void sort_block(int belong){
	Ordered_Array[belong]=Unordered_Array[belong];dirty[belong]=1;
	sort(Ordered_Array[belong].begin(),Ordered_Array[belong].end());
}
int ASK(int l,int r,int c){
	int ans=LLONG_MIN;
	if(Belong[l]==Belong[r]){
		for(int i=l;i<=r;i++)if(Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]<c)ans=max(ans,Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]);
	}else{
		for(int i=l;i<=Right[Belong[l]];i++)if(Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]<c)ans=max(ans,Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]);
		for(int i=Belong[l]+1;i<=Belong[r]-1;i++){
			if(!dirty[i])sort_block(i);
			if(Ordered_Array[i][0]>=c-add[i])continue;
			ans=max(ans,*(lower_bound(Ordered_Array[i].begin(),Ordered_Array[i].end(),c-add[i])-1)+add[i]);
		}
		for(int i=Left[Belong[r]];i<=r;i++)if(Unordered_Array[Belong[r]][i-Left[Belong[r]]]+add[Belong[r]]<c)ans=max(ans,Unordered_Array[Belong[r]][i-Left[Belong[r]]]+add[Belong[r]]);
	}
	if(ans==LLONG_MIN)return -1;
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++)cin>>a[i];
	init();
	for(int i=1;i<=N;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0)addv(l,r,c);
		if(opt==1)cout<<ASK(l,r,c)<<endl;
	}
	return 0;
}
CPP
if(Belong[l]==Belong[r]){
		for(int i=l;i<=r;i++)if(Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]<c)ans=max(ans,Unordered_Array[Belong[l]][i-Left[Belong[l]]]+add[Belong[l]]);
	}else{
if内为何不能压行?

回复

17 条回复,欢迎继续交流。

正在加载回复...