代码出现神秘 RE,求调
查看原帖
代码出现神秘 RE,求调
470769
DengStar楼主2024/9/12 19:46

我在尝试实现封装版本的动态开点线段树,但是出现了神秘的错误。错误部分的代码如下:

template<class Info, class Tag>
struct SegTree // 动态开点线段树
{
	const int n; // 序列长度
	int rt, tot; // 节点数量 
	vector<Info> info;
	vector<Tag> tag;
	vector<int> lson, rson;
	
	SegTree(int _n): n(_n), rt(0), tot(0), info(1), tag(1), lson(100), rson(100) {}
	
	void apply(int &id, const Tag &v, int l, int r)
	{
//		if(!id) newNode(id, l, r);
		debug("In apply(before newNode): id = %d\n", id); 
		if(!id)
		{
			id = ++tot;
			debug("id = %d, tot = %d\n", id, tot);
			info.emplace_back(l, r);
			tag.push_back(Tag());
			lson.push_back(0), rson.push_back(0);
//			lson.resize(id + 1, 0), rson.resize(id + 1, 0);
			debug("lson.size() = %d, rson.size() = %d\n", (int)lson.size(), (int)rson.size());
			d
		debug("In apply: id = %d, [l, r] = [%d, %d]\n", id, l, r);
//		tag[id].apply(v);
		tag.at(id).apply(v);
//		info[id].apply(v, l, r);
		info.at(id).apply(v, l, r);
	}
};

apply 是一个用于下放 tag 的函数,在此函数中,首先判定当前节点是否为空,如果为空(id == 0),那么就新建节点(使 id = ++tot,并使 taginfolsonrson 这几个 vector 扩容)。
在测试样例的过程中,当 id == 0 时,apply 函数出现了错误的反应:id 被设为了一个极大的不确定的值(比如 262406480)。输出中间变量发现,在 id = ++tot 这一行,id 确实被设为了正确的值,并且直到 tag.push_back(Tag()); 这一行仍是正确的。但执行了 lson.push_back(0), rson.push_back(0); 这一行之后,id 的值就被改变了。
后来我尝试在 SegTree 的构造函数中把 lsonrson 的大小设为 100,并把出错的那一行改为 lson.resize(id + 1, 0), rson.resize(id + 1, 0);,这时 id 的值就对了。**这个问题是不是 vector 扩容引起的?**如果是,应该如何规避?希望各位得到大佬的解答。
以下附上完整代码及测试样例时的输出:link

2024/9/12 19:46
加载中...