BZOJ 4826 [Hnoi2017] 影魔

发布于 2017-12-24  694 次阅读


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

题意:见原题面。


这题 的加强版。

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

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

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

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

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

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

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

 


一个非常弱的准退役OIER