当前位置: 代码迷 >> 综合 >> ssl例5
  详细解决方案

ssl例5

热度:41   发布时间:2023-10-09 12:59:33.0
一行N个方格,开始每个格子里的数都是0。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子区间[a,b]中所有元素的和;修改的规则是指定某一个格子x,加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N≤1024,提问和修改的总数可能达到60000条。
题解:
题目中的区间是以元素为端点,因此[a,b]和[b,c]存在重合,这和我们之前讨论的区间定义不同。我们这里忽略预处理过程,直接使用之前的区间定义。

代码:
if (l=a) and (r=b)
    then count:=tree[p].count
    else begin
           m:=(l+r) div 2;
           if b<=m
             then count:=count(p*2,l,m,a,b)
             else if a>=m then count:=count(p*2+1,m,r,a,b)
                          else count:=count(p*2,l,m,a,m)+count(p*2+1,m,r,m,b);
         end
  相关解决方案