求助关于分块的一个问题

P3372 【模板】线段树 1

Qerucy @ 2023-10-03 23:11:12

rt,以下两段代码:

for(int i=1;i<=n;i++){
        ad[i]=(i-1)/B+1;
        sum[ad[i]]+=a[i];
        if((i-1)%B==0) st[++cnt]=i;
        if(i%B==0) ed[cnt]=i;
    }
if(n%B!=0) ed[cnt]=n;
for(int i=1;i<=n;i++){
        ad[i]=(i-1)/B+1;
        sum[ad[i]]+=a[i];
        if((i-1)%B==0) st[++cnt]=i;
        if(i%B==0) ed[cnt]=i;
    }
//if(n%B!=0) ed[cnt]=n;

为啥两段代码交上去都能 A 啊,是数据太水还是这种不用设最后一个块的右边界是对的?


by Qerucy @ 2023-10-03 23:13:00

完整代码:

https://www.luogu.com.cn/paste/t47m30v4


by bamboo12345 @ 2023-10-03 23:17:15

感觉其实也没啥毛病,就是等同于最后多了一堆为0且一定不会修改的元素


by VividCycle @ 2023-10-03 23:32:18

@iyag 有啥问题


by FxorG @ 2023-10-03 23:41:25

某些情况下可能会挂掉,比如你求序列 min,然后初始化块的时候会有 0。


by Wf_yjqd @ 2023-10-03 23:43:23

主要取决于分块实现方法和题目维护的东西吧。

确实有些题是能卡掉没卡的


|