关于本题线段树一些问题总结
查看原帖
关于本题线段树一些问题总结
308796
LoserKugua楼主2022/10/5 19:03

(不一定按下面分值,都可以看一下)(hack数据由于本蒟蒻太菜造不出来。。。)

1.如果样例2都过不去则需要一个变量记录一下是否有区间修改标记下传,修改时修改这个变量为true,下传标记时判断一下这个变量是否为true,传完记得改回false(也可以通过初始赋值区间修改标记为无穷大,下传标记时判断是不是无穷大来实现)(推荐后面一种方式,因为我用前面的实现方式时没有同时改左右子树的变量为true,出问题了)

2.如果WA on #5~#10,检查一下线段树存储有没有开long long,毕竟1e9如果拉满三次就爆int了,还有一个可能就是用于查询函数等的无穷大设置可能不够大,应为9223372036854775807(2^63-1)

3.如果WA on #6~#10,也就是最普遍的60pts,根据数据梯度不难发现一般就是修改操作的问题,考虑以下几点:

·修改函数递归到当前区间完全覆盖时有没有把加法标记清空,或者下传修改标记时有没有把左右子树的加法标记清空

·下传标记的顺序应该是先区间修改再下传加法标记

4.如果TLE了,考虑卡常(非线段树不太会卡常):乘法改位运算(p2 -> p<<1, p2+1 -> p<<1|1),不必要的变量不开long long比如左右边界,节点编号等,使用较快的输入输出:

快读(isdigit(x) 可改为 x>='0' && x<='9')

int ffread(){
	int ret = 0,f = 1;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(isdigit(c)) {
		ret = (ret << 1) + (ret << 3) + c - 48;
		c = getchar();
	}
	return ret * f;
}

快输

void ffout(long long x){
    if(x<0) {
    	x = -x;
      putchar('-');
    }
    short sta[31],top = 0;
    do
    {
        sta[top++]=  x%10;
        x /= 10;
    }while(x);
    while(top) putchar(sta[--top]+'0');
}
2022/10/5 19:03
加载中...