biophitma_wby @ 2024-11-14 21:26:10
自己造的样例都过了，提交后20pts。（程序中有输出函数）
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,Inf=0x7f7f7f7f;
struct Tree{
int ls,rs;
int maxx;
int condition=-1;//-1表示未操作,0表示先已进行cover,1表示先已进行add;
int tag_cover=-Inf,tag_add=0;
}tree[4*N];
inline void down(int k){
if(tree[k].condition==0){
tree[2*k].condition=tree[2*k+1].condition=0;
tree[2*k].tag_cover=tree[2*k+1].tag_cover=tree[k].tag_cover;
tree[2*k].tag_add+=tree[k].tag_add;
tree[2*k+1].tag_add+=tree[k].tag_add;
tree[2*k].maxx=tree[k].tag_cover+tree[k].tag_add;
tree[2*k+1].maxx=tree[k].tag_cover+tree[k].tag_add;
tree[k].tag_add=0;
tree[k].tag_cover=-Inf;
tree[k].condition=-1;
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}else if(tree[k].condition==1){
tree[2*k].condition=tree[2*k+1].condition=1;
if(tree[k].tag_cover!=-Inf){
tree[2*k].maxx=tree[k].tag_cover;
tree[2*k+1].maxx=tree[k].tag_cover;
tree[2*k].tag_add+=tree[k].tag_add;
tree[2*k+1].tag_add+=tree[k].tag_add;
tree[2*k].tag_cover=tree[2*k+1].tag_cover=tree[k].tag_cover;
tree[k].tag_add=0;
tree[k].tag_cover=-Inf;
tree[k].condition=-1;
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}else{
tree[2*k].maxx+=tree[k].tag_add;
tree[2*k+1].maxx+=tree[k].tag_add;
tree[2*k].tag_add+=tree[k].tag_add;
tree[2*k+1].tag_add+=tree[k].tag_add;
tree[2*k].tag_cover=tree[2*k+1].tag_cover=tree[k].tag_cover;
tree[k].tag_add=0;
tree[k].tag_cover=-Inf;
tree[k].condition=-1;
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
}
}
inline void build(int k,int l,int r){
tree[k].ls=l,tree[k].rs=r;
if(l==r){
scanf("%d",&tree[k].maxx);
tree[k].condition=-1;
tree[k].tag_add=0;
tree[k].tag_cover=-Inf;
return;
}
int mid=(l+r)>>1;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
inline void cover_interval(int k,int l,int r,int data){
if(l<=tree[k].ls&&tree[k].rs<=r){
tree[k].maxx=data;
tree[k].tag_cover=data;
if(tree[k].condition==-1)tree[k].condition=0;
return;
}
if(tree[k].condition!=-1)down(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)cover_interval(2*k,l,r,data);
if(mid<r)cover_interval(2*k+1,l,r,data);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
inline void add_interval(int k,int l,int r,int add){
if(l<=tree[k].ls&&tree[k].rs<=r){
tree[k].maxx+=add;
tree[k].tag_add=add;
if(tree[k].condition==-1)tree[k].condition=1;
return;
}
if(tree[k].condition!=-1)down(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)add_interval(2*k,l,r,add);
if(mid<r)add_interval(2*k+1,l,r,add);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
inline int ask_max(int k,int l,int r){
int maxx=-Inf;
if(l<=tree[k].ls&&tree[k].rs<=r){
return tree[k].maxx;
}
if(tree[k].condition!=-1)down(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)maxx=max(maxx,ask_max(2*k,l,r));
if(mid<r)maxx=max(maxx,ask_max(2*k+1,l,r));
return maxx;
}
inline int ask_point(int k,int x){
if(tree[k].ls==tree[k].rs){
return tree[k].maxx;
}
if(tree[k].condition!=-1)down(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(x<=mid)return ask_point(2*k,x);
else return ask_point(2*k+1,x);
}
int main(){/*
freopen("file.in","r",stdin);
freopen("file.out","w",stdout);*/
int n,q;scanf("%d%d",&n,&q);
build(1,1,n);/*
for(int j=1;j<=n;j++){
printf("%d ",ask_point(1,j));
}printf("\n");*/
while(q--){
int op,l,r,x;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%d",&x);
cover_interval(1,l,r,x);
}else if(op==2){
scanf("%d",&x);
add_interval(1,l,r,x);
}else{
printf("%d\n",ask_max(1,l,r));
}
for(int j=1;j<=n;j++){
printf("%d ",ask_point(1,j));
}printf("\n");
}
return 0;
}by biophitma_wby @ 2024-11-18 19:49:48
已过，此贴完。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const long long Inf=0x7f7f7f7f7f7f7f7f;
int n,q;
int op,l,r;ll x;
struct Tree{
int ls,rs;
ll maxx,lazzy;
int used=0;
}tree[N<<2];
void pushdown(int k){
if(tree[k].used==1){
tree[2*k].maxx=tree[2*k+1].maxx=tree[k].lazzy;
tree[2*k].lazzy=tree[2*k+1].lazzy=tree[k].lazzy;
tree[2*k].used=tree[2*k+1].used=1;
tree[k].used=0,tree[k].lazzy=0;
}else{
tree[2*k].maxx+=tree[k].lazzy;
tree[2*k+1].maxx+=tree[k].lazzy;
if(!tree[2*k].used){
tree[2*k].lazzy=tree[k].lazzy;
tree[2*k].used=2;
}else tree[2*k].lazzy+=tree[k].lazzy;
if(!tree[2*k+1].used){
tree[2*k+1].lazzy=tree[k].lazzy;
tree[2*k+1].used=2;
}else tree[2*k+1].lazzy+=tree[k].lazzy;
tree[k].used=0,tree[k].lazzy=0;
}
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void build(int k,int l,int r){
tree[k].ls=l,tree[k].rs=r;
if(l==r){
scanf("%lld",&tree[k].maxx);
tree[k].lazzy=0;
tree[k].used=0;
return;
}
int mid=(l+r)>>1;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void cover_interval(int k,int l,int r,ll data){
if(l<=tree[k].ls&&tree[k].rs<=r){
tree[k].maxx=data;
tree[k].lazzy=data;
tree[k].used=1;
return;
}
if(tree[k].used)pushdown(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)cover_interval(2*k,l,r,data);
if(mid<r)cover_interval(2*k+1,l,r,data);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void add_interval(int k,int l,int r,int data){
if(l<=tree[k].ls&&tree[k].rs<=r){
tree[k].maxx+=data;
if(!tree[k].used){
tree[k].lazzy=data;
tree[k].used=2;
}else{
tree[k].lazzy+=data;
}
return;
}
if(tree[k].used)pushdown(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)add_interval(2*k,l,r,data);
if(mid<r)add_interval(2*k+1,l,r,data);
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
ll ask_point(int k,int x){
if(tree[k].ls==tree[k].rs){
return tree[k].maxx;
}
if(tree[k].used)pushdown(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(x<=mid)return ask_point(2*k,x);
else return ask_point(2*k+1,x);
}
ll ask_max_interval(int k,int l,int r){
ll maxx=-Inf;
if(l<=tree[k].ls&&tree[k].rs<=r){
return tree[k].maxx;
}
if(tree[k].used)pushdown(k);
int mid=(tree[k].ls+tree[k].rs)>>1;
if(l<=mid)maxx=max(maxx,ask_max_interval(2*k,l,r));
if(mid<r)maxx=max(maxx,ask_max_interval(2*k+1,l,r));
return maxx;
}
int main(){
scanf("%d%d",&n,&q);
build(1,1,n);
while(q--){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%lld",&x);
cover_interval(1,l,r,x);
}else if(op==2){
scanf("%lld",&x);
add_interval(1,l,r,x);
}else {
printf("%lld\n",ask_max_interval(1,l,r));
}/*
for(int i=1;i<=n;i++){
printf("%lld ",ask_point(1,i));
}printf("\n");*/
}
return 0;
}