警钟撅烂
查看原帖
警钟撅烂
678175
jqQt0220楼主2024/10/24 18:20

如果你像我这样写线段树:

namespace segtree
{
	struct node
	{
		int l,r;
		ll sum,tag;
		int len(){return r-l+1;}
	}tr[_mxn<<2];
	inline int ls(int p){return p<<1;}//注意这里
	inline int rs(int p){return p<<1|1;}//注意这里
	void pushup(int p)
	{
		tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
	}
	void build(int p,int l,int r)
	{
		tr[p].l=l,tr[p].r=r;
		tr[p].tag=0;
		if(l==r)
		{
			tr[p].sum=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		pushup(p);
	}
	void pushdown(int p)
	{
		ll t=tr[p].tag;
		tr[p].tag=0;
		tr[ls(p)].sum+=t*tr[ls(p)].len();
		tr[rs(p)].sum+=t*tr[rs(p)].len();
		tr[ls(p)].tag+=t;
		tr[rs(p)].tag+=t;
	}
	void update(int p,int l,int r,ll k)
	{
		if(l<=tr[p].l&&tr[p].r<=r)
		{
			tr[p].sum+=k*tr[p].len();
			tr[p].tag+=k;
			return;
		}
		pushdown(p);
		int mid=(tr[p].l+tr[p].r)>>1;
		if(l<=mid)
			update(ls(p),l,r,k);
		if(mid<r)
			update(rs(p),l,r,k);
		pushup(p);
	}
	ll query(int p,int l,int r)
	{
		if(l<=tr[p].l&&tr[p].r<=r)
			return tr[p].sum;
		pushdown(p);
		int mid=(tr[p].l+tr[p].r)>>1;
		ll res=0;
		if(l<=mid)
			res+=query(ls(p),l,r);
		if(mid<r)
			res+=query(rs(p),l,r);
		return res;
	}
	int queryp(int p,int l,int r,int rd,ll w)
	{
		if(l==r)
			return l;
		pushdown(p);
		int mid=(l+r)>>1;
		ll h=tr[ls(p)].sum*(1ll<<rd);
		if(w>h)
			return queryp(rs(p),mid+1,r,rd,w-h);
		else
			return queryp(ls(p),l,mid,rd,w);
	}
}

那么我标注的地方的函数一定要加 inline 或者用 #define,不然会 T 飞

2024/10/24 18:20
加载中...