求助vector 树套树
  • 板块学术版
  • 楼主_HL_
  • 当前回复12
  • 已保存回复12
  • 发布时间2022/11/20 20:21
  • 上次更新2023/10/27 02:09:38
查看原帖
求助vector 树套树
223560
_HL_楼主2022/11/20 20:21

为什么 resize 和不 resize 结果不一样 调心态崩了。

struct TT
{
	signed n,rt[N],tot;
	stack<signed>fw;
	#define lb x&-x
	struct seg
	{
		int sum;
		signed son[2];
	};
	seg zero;
	vector<seg>t;
	inline void init(int _n)
	{
		n=_n;
		zero.sum=zero.son[0]=zero.son[1]=0;
		t.pb(zero);
		//t.resize(N);//<======这里
	}
	#define ls t[p].son[0]
	#define rs t[p].son[1]
	signed nwnd()
	{
		t.pb(zero);
		return ++tot;
	}
	inline void update(signed p)
	{
		t[p].sum=t[ls].sum+t[rs].sum;
	}
	void CHK(signed &p){return;if(!t[p].sum)fw.push(p),p=0;}
	void modify(int l,int r,int x,int v,signed &p)
	{
		if(!p)p=nwnd();
		if(l==r)return t[p].sum=v,CHK(p),void();
		int mid=l+r>>1;
		if(x<=mid)modify(l,mid,x,v,ls);
		else modify(mid+1,r,x,v,rs);
		update(p),CHK(p);
	}
	int query(int l,int r,int ql,int qr,signed p)
	{
		if(!p)return 0;
		if(ql<=l&&r<=qr),t[p].sum;
		int mid=l+r>>1,res=0;
		if(ql<=mid)res+=query(l,mid,ql,qr,ls);
		if(qr>mid)res+=query(mid+1,r,ql,qr,rs);
		return res;
	}
	void ins(int x,int y,int v)
	{
		for(;x<=n;x+=lb)modify(1,n,y,v,rt[x]);
	}
	int ask(int x,int l,int r)
	{
		int res=0;
		for(;x;x-=lb)res+=query(1,n,l,r,rt[x]);
		return res;
	}
}S,P;
2022/11/20 20:21
加载中...