(不一定按下面分值,都可以看一下)(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');
}