社区讨论
为何不能压行
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;
}
CPPif(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 条回复,欢迎继续交流。
正在加载回复...