主题

主题

 
   

一个处理区间修改的非数据结构思想

  • 扯淡

看到了那位与魔女契约的candy(orz跪烂)一篇经验之谈。然后自己去尝试了一下。


  • 一个例子

拿codevs_1082(一个被我搞来搞去的题……)举例子吧。

给出一个长度为n的序列,要求支持:

  1. 给[li..ri]的权值+w

  2. 查询[li..ri]的权值

(吐槽:这不是傻逼线段树模板题?这么菜的题目liaoy还拿出来讲?liaoy这个菜鸡)


 

  • 想法

我们考虑一种不用Seg,BIT以及Splay等诸多数据结构的想法。

我们用分治来思考这个问题。

(好吧CDQ分治)

一个单点修改区间查询的是可以CDQ分治轻而易举完成。

但区间修改变得不那么可做。

我们发现,之所以不好做的原因是一个修改是通过多个点来造成贡献的,那么我们瓶颈在于如何处理出一个修改对应的多个点贡献。

我们需要把一个询问和查询都拆分为前缀的询问与前缀的查询。


  • 差分的方法

在处理左边的部分的时候,我们把区间加法变为差分之后的单点修改。之后我们坐一趟前缀和即可。

扫描右边的一部分,然后记录一个距离啥的即可。


  • 直接计算的方法

上一个差分是一个处理。事实上我们可以通过直接维护和和距离来计算贡献。


这两个方法我们可以看一个图:


黄色线左边是曾经计算过的贡献,现在考虑计算黄色线右边的部分。红色的为修改,绿色的为查询。

不难发现,在一个端点部分,四个修改都会有贡献。过了第一个红色修改的端点,就变为了三个修改的贡献。

这样我们用一个val记录当前移动一个单位的贡献,sum记录当前的修改的总贡献。同时记录一下与上一个位置的距离。就可以O(n)计算贡献了。

    for(tl=l; tl<=m; tl++)if(!Q[tl].opt)val+=Q[tl].w;

    for(tl=l,tr=m+1; tr<=r; tr++) {

        if(!Q[tr].opt)continue;

        while(Q[tl].x<=Q[tr].x&&tl<=m) {

            if(!Q[tl].opt) {

                sum+=val*(Q[tl].x-last);  last=Q[tl].x;  val-=Q[tl].w;

            }

            tl++;

        }

        Ans[Q[tr].w]+=(sum+val*(Q[tr].x-last))*Q[tr].opt;

    }

大致代码如上。


  • 杂谈

codevs_1082上跑了800ms+,超越了之前我写的所有的数据结构(可能是本蒟写丑了),不像candy所说,常数又大,又是离线……

candy所说第二部分:

可以推广到一系列区间修改与查询问题

也许很有思考意义。


最后附上candy的博客,本蒟的处理方法与其稍有不同:

http://www.cnblogs.com/candy99/p/cdqrange.html

再附上本蒟丑陋的代码:

https://code.csdn.net/snippets/2290133

 
 
评论
 
 
热度(1)