[BZOJ2253][2010 Beijing wc]纸箱堆叠（CDQ分治优化DP）
考虑一个朴素的DP方案： 先求出所有纸箱的最短边（以下第 i 个纸箱的最短边记为 xi ），次短边（以下第 i 个纸箱次短边记为 yi ）和最长边（以下记为 zi ），然后按照 xi 从小到大排序。 这样，就变成了一个求...
bzoj1492/luogu4027 货币兑换 (斜率优化+cdq分治)
设f[i]是第i天能获得的最大钱数，那么f[i]=max{在第j天用f[j]的钱买，然后在第i天卖得到的钱，f[i-1]}然后解一解方程什么的，设$x[j]=\frac{F[j]}{A[j]*Rate[j]+B[j]}$，$y[j]=Rate[j]*x[j]$的话，就能得到$f[i]=max\{y[...
luogu3810 陌上花开 (cdq分治)
求三维偏序设三维为a,b,c。先对a排序，这样i的偏序就只能<i。然而排序的时候需要三个维度都判断一遍，最后还要去重，不然会出现实际应该记答案的数出现在它后面的情况。（排序用的函数里不要写类似于<=之类的东西啊..会出奇奇怪怪的问题的(RE)）然后分治来做，我们在做区间[l,r]的时候，...
BZOJ 2726: [SDOI2012]任务安排( dp + cdq分治 )
考虑每批任务对后面任务都有贡献, dp(i) = min( dp(j) + F(i) * (T(i) - T(j) + S) ) (i < j <= N) F, T均为后缀和. 与j有关的量只有t = dp(j) - F(i) * T(j) , 我们要最小化它. dp(j)->y...
BZOJ 2683: 简单题 [CDQ分治]
同上题那你为什么又发一个？因为我用另一种写法又写了一遍...不用排序，$CDQ$分治的时候归并排序快了1000ms...#include<iostream>#include<cstdio>#include<algorithm>#include<cstring...
BZOJ_3295_[Cqoi2011]动态逆序对_CDQ分治+树状数组
BZOJ_3295_[Cqoi2011]动态逆序对_CDQ分治+树状数组Description对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数Input输...
bzoj3295: [Cqoi2011]动态逆序对(cdq分治+树状数组)
3295:[Cqoi2011]动态逆序对题目：传送门题解：刚学完cdq分治，想起来之前有一道是树套树的题目可以用cdq分治来做...尝试一波还是太弱了...想到了要做两次cdq...然后伏地膜大佬其实需要维护的地方还是很容易想到的：第一维维护位置w，第二维维护数值s，第三维维护修改的时间t。那么对于...
HDU 5730 Shell Necklace（CDQ分治+FFT）
Description给出长度分别为1~n的珠子，长度为i的珠子有a[i]种，每种珠子有无限个，问用这些珠子串成长度为n的链有多少种方案Input多组用例，每组用例首先输入一整数n表示链长，之后n个整数ai表示长度为i的珠子种类数，以n=0结束输入(n<=10^5,0<=ai<=1...
HDU 3507 Print Article（CDQ分治+分治DP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=3507【题目大意】将长度为n的数列分段，最小化每段和的平方和。【题解】根据题目很容易得到dp[j]=min(dp[k]+(s[j]-s[k])2)，因为是从前往后转移，且决策单调，因此在CDQ分治的同...
[BZOJ2225][SP2371]LIS2 - Another Longest Increasing Subsequence Problem：CDQ分治+树状数组
分析这回试了一下三级标题，不知道效果怎么样？回到正题，二维最长上升子序列......嗯，我会二维线段树。考虑\(CDQ\)分治，算法流程：先递归进入左子区间。将左，右子区间按\(x\)排序。归并处理左右子区间，在过程中使用树状数组加速\(DP\)。还原右区间，清空树状数组。递归进入右子区间。代码#i...
【CF553E】Kyoya and Train 最短路+cdq分治+FFT
【CF553E】KyoyaandTrain题意：有一张$n$个点到$m$条边的有向图，经过第i条边要花$c_i$元钱，经过第i条边有$p_{i,k}$的概率要耗时k分钟。你想从1走到n，但是如果整个过程耗时超过了$t$，则需要额外花费$f$元。求从1走到n的期望最小花费。$n\le50,m\le10...
[BZOJ3295][Cqoi2011]动态逆序对 CDQ分治&树套树
3295:[Cqoi2011]动态逆序对TimeLimit: 10Sec MemoryLimit: 128MBDescription对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元...
bzoj3110: [Zjoi2013]K大数查询 【cdq分治&树套树】
模板题，折腾了许久。cqd分治整体二分，感觉像是把询问分到答案上。#include<bits/stdc++.h>#definerep(i,a,b)for(inti=a;i<=b;i++)#definedrep(i,a,b)for(inti=a;i>=b;i--)#define...
一篇自己都看不懂的CDQ分治&整体二分学习笔记
作为一个永不咕咕咕的博主，我来更笔记辣qaqCDQ分治CDQ分治的思想还是比较简单的。它的基本流程是：\(1.\)将所有修改操作和查询操作按照时间顺序并在一起，形成一段序列。显然，会影响查询操作结果的修改操作在序列中一定会在这一个查询操作前面\(2.\)将这一段序列分为左右两半，递归解决左右两半的子...
【BZOJ-3262】陌上花开 CDQ分治（3维偏序）
3262:陌上花开TimeLimit: 20Sec MemoryLimit: 256MBSubmit: 1439 Solved: 648[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每...
COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]
传送门给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。对于100%的数据，1<=n<=50000，保证所有的ai、bi、ci分别组成三个1~n的排列。$CDQ$...