Story_of_CT @ 2024-03-02 11:17:47
请问线段树有什么误区会导致常数大幅增加吗?
10 2.19s结束
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long dat;
dat input[2000005];
int n,q;
struct node{
node*lchild,*rchild;
int lnum,rnum;
bool isseet,isadd;
dat num;
dat maxunder;
node(int l,int r){
lnum=l;rnum=r;isseet=isadd=false;
if(l==r)
{maxunder=num=input[l];lchild=rchild=NULL;isseet=true;return;}
int t=(l+r-1)/2;
if(l>n)return;
lchild=new node(l,t);rchild=new node(t+1,r);
maxunder=max(lchild->maxunder,rchild->maxunder);
}
void sink(){
//system("pause");
if((!(isseet||isadd))||lnum==rnum)return;
if(isseet){
isseet=false;
node*t=lchild;
t->isadd=false;t->isseet=true;t->num=t->maxunder=num;
t=rchild;
t->isadd=false;t->isseet=true;t->num=t->maxunder=num;
return;
}
if(isadd){
isadd=false;
node*t=lchild;
if(!(t->isseet||t->isadd)){t->isadd=true;t->num=0;}
t->num+=num;t->maxunder+=num;
t=rchild;
if(!(t->isseet||t->isadd)){t->isadd=true;t->num=0;}
t->num+=num;t->maxunder+=num;
return;
}
}
void seet(int l,int r,dat x){
if(l==lnum&&r==rnum){
isseet=true;isadd=false;num=maxunder=x;return;
}
sink();
int t=(lnum+rnum-1)/2;
if(l<=t)lchild->seet(l,min(t,r),x);
if(r>=t+1)rchild->seet(max(t+1,l),r,x);
maxunder=max(lchild->maxunder,rchild->maxunder);
}
void add(int l,int r,dat x){
if(l==lnum&&r==rnum){
if(!(isseet||isadd)){isadd=true;num=0;}
num+=x;maxunder+=x;return;
}
sink();
int t=(lnum+rnum-1)/2;
if(l<=t)lchild->add(l,min(t,r),x);
if(r>=t+1)rchild->add(max(t+1,l),r,x);
maxunder=max(lchild->maxunder,rchild->maxunder);
}
dat search(int l,int r){
if(l==lnum&&r==rnum)return maxunder;
sink();
int t=(lnum+rnum-1)/2;
dat ans;
if(l<=t)ans=lchild->search(l,min(t,r));
if(r>=t+1){
if(l>t)ans=rchild->search(max(t+1,l),r);
else ans=max(ans,rchild->search(max(t+1,l),r));
}
return ans;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>input[i];
int l,r,x=1;
for(x=1;x<n;x*=2);
node tree(1,x);
for(int i=1;i<=q;i++){
int op;cin>>op;
if(op==1){cin>>l>>r>>x;tree.seet(l,r,x);continue;}
if(op==2){cin>>l>>r>>x;tree.add(l,r,x);continue;}
if(op==3){cin>>l>>r;cout<<tree.search(l,r)<<endl;continue;}
}
}
by Story_of_CT @ 2024-03-03 13:53:33
AC 修改内容主要是搜索时可以不下沉标记 代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long dat;
dat input[2000005];
int n,q;
struct node{
node*lchild,*rchild;
int lnum,rnum;
bool isadd;
dat num;
dat maxunder;
node(int l,int r){
lnum=l;rnum=r;isadd=true;num=0;
if(l==r)
{maxunder=num=input[l];lchild=rchild=NULL;isadd=false;return;}
int t=(l+r-1)/2;
if(l>n)return;
lchild=new node(l,t);rchild=new node(t+1,r);
maxunder=max(lchild->maxunder,rchild->maxunder);
}
void sink(){
//system("pause");
if((isadd&&num==0)||lnum==rnum)return;
if(!isadd){
isadd=true;
node*t=lchild;
t->isadd=false;t->num=t->maxunder=num;
t=rchild;
t->isadd=false;t->num=t->maxunder=num;
num=0;
return;
}
if(isadd){
node*t=lchild;
t->num+=num;t->maxunder+=num;
t=rchild;
t->num+=num;t->maxunder+=num;
num=0;
return;
}
}
void seet(int l,int r,dat x){
if(l==lnum&&r==rnum){isadd=false;num=maxunder=x;return;}
sink();
int t=(lnum+rnum-1)/2;
//cout<<1<<endl;system("pause");
if(l<=t)lchild->seet(l,min(t,r),x);
//cout<<2<<endl;system("pause");
if(r>=t+1)rchild->seet(max(t+1,l),r,x);
//cout<<3<<endl;system("pause");
maxunder=max(lchild->maxunder,rchild->maxunder);
}
void add(int l,int r,dat x){
if(l==lnum&&r==rnum){num+=x;maxunder+=x;return;}
sink();
int t=(lnum+rnum-1)/2;
if(l<=t)lchild->add(l,min(t,r),x);
if(r>=t+1)rchild->add(max(t+1,l),r,x);
maxunder=max(lchild->maxunder,rchild->maxunder);
}
dat search(int l,int r){
if((l==lnum&&r==rnum)||!isadd)return maxunder;
int t=(lnum+rnum-1)/2;
dat ans;
if(l<=t)ans=lchild->search(l,min(t,r));
if(r>=t+1){
if(l>t)ans=rchild->search(max(t+1,l),r);
else ans=max(ans,rchild->search(max(t+1,l),r));
}
return ans+num;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>input[i];
int l,r,x=1;
for(x=1;x<n;x*=2);
node tree(1,x);
for(int i=1;i<=q;i++){
int op;cin>>op;
if(op==1){cin>>l>>r>>x;tree.seet(l,r,x);continue;}
if(op==2){cin>>l>>r>>x;tree.add(l,r,x);continue;}
if(op==3){cin>>l>>r;cout<<tree.search(l,r)<<endl;continue;}
}
}
by Bamboo2022 @ 2024-04-10 15:58:18
同问