wcwswswws的日记

wcwswswws

CF 91 一点记录。

又是算法想的出手速跟不上。纠结是d还是e也纠结了一会。把我想的算法贴一下,或许是我想的太挫了才导致没调对。

D的意思是:给你n(<=10^5)个线段,有1种操作:某条线段[l,r]变成[l+1,r+1]或者[l-1,r-1]。最多操作k次。问最多能包含几个LN。
    算法:
    二分枚举答案(log(2^19)),对于每个答案,从左往右枚举合法区间,时间复杂度O(mlogm)。枚举前线段排序。对于每次右移,将需要右移才能包含的线段和需要左移包含的线段是可以只用一个数组记录的,每次左移对于已经在左边或右边不包含当前或移动到左边的值加入的结果维护是常数的。对于包含的情况用个小根堆维护,key为右端点。这样由于右到左就一次,所以时间复杂度为O(nlognlogm)。
   E的意思是:给一个序列,两种操作:add l,r,d,a[l]~a[r]均+d;count l,r,a[l]~a[r]有几个LN。
    算法:线段树。先将add按li排序,然后a从左往右扫描并维护包含当前点i的add值。这里用到第一个线段树,用来记录对该点有影响的add的线段以及该add起效后的情况。满足条件的LN大概有20个左右,我们用每个LN依次减去a[i],然后在线段树中查等于该值的add以及下一个add,并将其构成线段集L。
    然后是统计结果。这个问题本质上是:在平面上给你n个平行于x轴的线段,和m个平行于y轴的线段,让你统计有多少个交点。x轴是命令编号,y轴是线段的坐标。这就是个明显的线段树了。

posted on 2011-10-28 01:48 世界厕所所长 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理