很糟糕,线段树学了一年了,打了不下100遍,到现在还是没有一遍不打错。
正在打树剖板子时,把下面这段代码(线段树的函数)换成之前线段树中AC的代码就能AC了,否则只有10分……但是,把两个代码对照了20遍,也没查出任何错误(眼瞎)……
本菜鸡求助大佬找错啊……只有几个函数,太感谢了!@ducati 菜鸡
inline void pushup(int rt)
{
tree[rt]=tree[2*rt]+tree[2*rt+1];
}
inline void build_tree(int rt,int l,int r)
{
if (l==r)
{
tree[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build_tree(2*rt,l,mid);
build_tree(2*rt+1,mid+1,r);
pushup(rt);
}
inline void f(int rt,int l,int r,int k)
{
tree[rt]+=(r-l+1)*k;
tag[rt]+=k;
}
inline void pushdown(int rt,int l,int r)
{
int mid=(l+r)>>1;
f(2*rt,l,mid,tag[rt]);
f(2*rt+1,mid+1,r,tag[rt]);
tag[rt]=0;
}
inline void change(int nl,int nr,int l,int r,int rt,int k)
{
if (nl<=l&&r<=nr)
{
f(rt,l,r,k);
return;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if (nl<=mid) change(nl,nr,l,mid,2*rt,k);
if (nr>mid) change(nl,nr,mid+1,r,2*rt+1,k);
pushup(rt);
}
inline int query(int nl,int nr,int l,int r,int rt)
{
pushdown(rt,l,r);
int mid=(l+r)>>1,ans=0;
if (nl<=l&&r<=nr) return tree[rt];
if (nl<=mid) ans+=query(nl,nr,l,mid,2*rt);
if (nr>mid) ans+=query(nl,nr,mid+1,r,2*rt+1);
return ans;
}