蒟蒻线段树代码求调qwq
查看原帖
蒟蒻线段树代码求调qwq
715233
Dino_chx楼主2022/8/26 13:36

就拿学的模板写的,为什么会WA啊

代码有亿点长,求大佬耐心看完

//segment tree
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define f 1LL
using namespace std;
const int N=1e5+10;
int tree[N<<2],lz[N];
inline int read()
{
int c=1,k=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
c=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
k=(k<<3)+(k<<1)+(ch^48);
ch=getchar();
}
return c*k;
}
inline int getmid(int l,int r)
{
return (l+r)>>1;
}
inline int lc(int x)
{
return x<<1;
}
inline int rc(int x)
{
return x<<1|1;
}
inline void push_up(int x)
{
tree[x]=tree[lc(x)]+tree[rc(x)];
return;
}
inline void init()
{
memset(tree,0,sizeof tree);
memset(lz,0,sizeof lz);
return;
}
//build 建树 
void build(int data,int l,int r)    //l r 管辖范围
{
if(l==r)
{
tree[data]=read();
return;
}
int mid=getmid(l,r);
build(lc(data),l,mid);
build(rc(data),mid+1,r);
push_up(data);
return;
} 
//push_down 懒标记下传 
void push_down(int data,int l,int r)
{
if(lz[data])
{
int mid=getmid(l,r);
lz[lc(data)]+=lz[data];
lz[rc(data)]+=lz[data];
tree[lc(data)]+=f*(mid-l+1)*lz[data];
tree[rc(data)]+=f*(r-mid)*lz[data];
lz[data]=0;
}
return;
}
//update 单点更新 
void update(int data,int l,int r,int k,int index)
{
if(l==r)
{
tree[data]+=k;       //自由更新 
return;
}
int mid=getmid(l,r);
push_down(data,mid-l+1,r-mid);
if(index<=mid)
update(lc(data),l,mid,k,index);
else
update(rc(data),mid+1,r,k,index);
push_up(data);
return;
}
//update_range 区间更新 
void update_range(int data,int l,int r,int tl,int tr,int k)
{
if(l<=tl&&r>=tr)
{
lz[data]+=f*k;
tree[data]+=f*(r-l+1)*k;
return;
}
push_down(data,tl,tr);
int mid=getmid(tl,tr);
if(mid>=l)
update_range(lc(data),l,r,tl,mid,k);
if(mid>r)
update_range(rc(data),l,r,mid+1,tr,k);
push_up(data);
}
//query_range 区间求和 
ll query_range(int data,int l,int r,int tl,int tr)
{
if(l<=tl&&r>=tr)
return tree[data];
push_down(data,tl,tr);
int mid=getmid(tl,tr);
ll ans=0;
if(mid>=l)
ans+=query_range(lc(data),l,r,tl,mid);
if(mid>r)
ans+=query_range(rc(data),l,r,mid+1,tr);
return ans;
}
int main()
{
int n,q;
n=read();
q=read();
build(1,1,n);
while(q--)
{
int opt;
opt=read();
if(opt==1)
{
int x,y,k;
x=read();
y=read();
k=read();
update_range(1,x,y,1,n,k);
}
else if(opt==2)
{
int x,y;
x=read();
y=read();
printf("%lld",query_range(1,x,y,1,n));
}
}
return 0;
}
2022/8/26 13:36
加载中...