分治

ac自动机(7) bitset(2) BSGS(1) dfs(3) DP(19) ODT(1) splay(1) ST表(2) tarjan(2) 中途相遇法(1) 主席树(4) 二分图(1) 二叉树(1) 分块(1) 回文树(1) 多校(1) 字符串(1) 容斥(2) 平衡树(5) 并查集(1) 快速乘(1) 数学(9) 整体二分(1) 树链剖分(2) 模拟退火(2) 水题(1) 爬山算法(1) 矩阵快速幂(2) 线性基(1) 线段树(10) 编译器(2) 背包(2) 莫队(1) 计算几何(1) 随机数(1) 高精度(1)

归档

标签

去牛客网

/ 注册

全部文章 / 分治（共3篇）

codeforces669E【CDQ分治】

地址很模板的CDQ分治题。需要考虑操作编号，操作时间，操作权值。对于询问要找同时小于编号和时间的操作才影响当前的询问。然后搞一下就行了。。甚至CDQ分治不用也行，树套树。。。还是很好理解的，外层权值，内层时间。 cf上路人的有点NB的树套树代码 map<int, map<in...

2019-07-19

0 436

[CQOI2011]动态逆序对【CDQ分治】

还是比较模板的题可是一开始没想出来。。之前电科校赛就遇到这道原题，今天终于补上了。。主要的思路还是计算出每个数对前面和后面的影响，然后删除的时候用总的减去就好了。。但是问题在于，对于删除操作怎么动态的维护前后关系：当删除一个数a[i]之后，要知道在1…i-1范围内有多少比a[i]大，在i+1…n...

2019-07-19

0 437

陌上花开【CDQ分治】

CDQ分治还是比较好理解的。先按照一维排序，对一维排序的数组分治，分治的话相当于降了一维我们只要考虑两个子区间里的数之间的大小关系，而不用考虑单个区间里面的数的影响（因为单区间里面的数已经被当成子问题解决了）这个时候我们就可以对两个区间按照第二维排序，因为左区间的所有第一维都是小于右区间的而且...

2019-07-16

0 390