BZOJ 4826 [Hnoi2017] 影魔


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4826

题意:见原题面。


这题 的加强版。

记\(pre_i\) 和\(nxt_i\) 分别表示

不同之处是第二种贡献怎么统计,枚举 i,发现分别固定\(pre_i\) 和\(nxt_i\) 后影响的都是一段连续的区间。

所以问题转化为矩形内单点加,线段加,矩形求和。

可以上二维数据结构了...?

两个 log 或者根号跑 20 万,死定了。

如果没有线段加就是简单的二维数点问题,怎么转换线段加呢,发现如果线段都是一个方向的就是在当前版本的主席树上区间加嘛...

于是按照行列分别维护两颗主席树即可,写了标记永久化... 直接推标记也是资词的。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4826 [Hnoi2017] 影魔


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,