警示后人(虽然可能没什么警示作用))
查看原帖
警示后人(虽然可能没什么警示作用))
534164
surfish楼主2024/10/24 21:29

如果你试图写一个通用的线段树模板,并使用了c++template定义线段树的类型,一定记得将所有参与运算的变量全部改成泛型

原70pts代码:

template<typename T, int maxN>
struct Segt{
	int size;
	T a[maxN];
	T sum[maxN * 4];
	T lzy[maxN * 4]; 
   // ...
	T _query(int start, int end, int id, int l, int r){
		if(l > end || r < start) return 0;
		if(l >= start && r <= end){
			return sum[id];
		}
		const int m = l + (r - l) / 2;
		if(lzy[id] != 0 && l != r){
			_push(id, l, r);
		}
		int s = 0; // 这里的s是左右节点的和,应该是T(本题中为undigned long long),但是我当时错误写成了int
		if(start <= m){
			s += _query(start, end, id * 2, l, m);
		}
		if(end > m){
			s += _query(start, end, id * 2 + 1, m + 1, r);
		}
		return s;
	}
	// ...
};

只需要将 int s = 0 改为 T s = 0 便可AC.

template<typename T, int maxN>
struct Segt{
	int size;
	T a[maxN];
	T sum[maxN * 4];
	T lzy[maxN * 4]; 
   // ...
	T _query(int start, int end, int id, int l, int r){
		if(l > end || r < start) return 0;
		if(l >= start && r <= end){
			return sum[id];
		}
		const int m = l + (r - l) / 2;
		if(lzy[id] != 0 && l != r){
			_push(id, l, r);
		}
		int s = 0; // 这里的s是左右节点的和,应该是T(本题中为undigned long long),但是我当时错误写成了int
		if(start <= m){
			s += _query(start, end, id * 2, l, m);
		}
		if(end > m){
			s += _query(start, end, id * 2 + 1, m + 1, r);
		}
		return s;
	}
	// ...
};

// uint64_t 是64位无符号整数,等价于unsigned long long
Segt<uint64_t, 100010> t;
// ...
2024/10/24 21:29
加载中...