如果我想实现:
-
区间修改,输入一个数 z,将范围内大于 z 的数修改为 z
-
单点查询
我想了一下可以维护一个 cov 标记来记录这个区间范围内的值是否相等
查询时如果 cov=1 直接返回,否则就 pushdown 之后向下走
那么由于我太弱了,想了一下觉得问一下比较好qwq:
-
这样做的正确性是否保证?
-
那我的 update 是不是该这么写:
{
if(x<=l&&r<=y)
{
....
tree[p].cov=1;
return;
}
tree[p].cov=0;
pushdown(p);
int mid=(l+r)>>1;
}
- 这样做的时间复杂度是否在 O(nlog2n) 以内?