14
2017-08
2017-08
ACdream 1157 Segments (CDQ分治)
将修改操作和查询操作分开来,每次都用左区间的修改操作更新右区间的查询操作,因为左区间的修改操作对左区间的查询操作在递归左区间时就已经处理了,同理查询操作也是一样。
写的太暴力,还能过程能优化很多
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
templ...
08月14日
3,332
14
2017-08
2017-08
UVALive 5871 Arnooks’s Defensive Line (CDQ分治)
在我们平常使用的分治中,每一个子问题只解决它本身(可以说是封闭的)。
而在cdq分治中,对于划分出来的两个子问题,前一个子问题用来解决后一个子问题而不是它本身。
具体算法流程如下:
1.将整个操作序列分为两个长度相等的部分(分)
2.递归处理前一部分的子问题(治1)
3.计算前一部分的子问题中的修改操作对后一部分子问题的影响(治2)
4.递归处理后一部分子问...
08月14日
3,380