关于 ~~毒瘤~~ 的线段树
  • 板块学术版
  • 楼主ducati
  • 当前回复18
  • 已保存回复18
  • 发布时间2020/8/1 13:24
  • 上次更新2023/11/6 21:36:03
查看原帖
关于 ~~毒瘤~~ 的线段树
87064
ducati楼主2020/8/1 13:24

很糟糕,线段树学了一年了,打了不下100遍,到现在还是没有一遍不打错。

正在打树剖板子时,把下面这段代码(线段树的函数)换成之前线段树中AC的代码就能AC了,否则只有1010分……但是,把两个代码对照了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;
}
2020/8/1 13:24
加载中...