题解 P2365 【任务安排】 算法:斜率优化动态规划 由于题解里没有关于的斜率优化做法,我打算写一下这种特殊的斜率优化动态规划 由于可以小于零,所以斜率不具有单调性,所以我们不能像原来一样维护下凸壳。我们不能只保留相邻两点斜率大于的部分,我们要把整个下凸壳都保留下来。这时队首也就不是最优解了，要二分找到一个左边比小,右边比大的位置。这个位置就是答案 #include<bits/stdc++.h> using namespace std; #define int long long const int N=500005; int l,r,n,s,t,c,j,sumt[N],sumc...

题解 P3242 【[HNOI2015]接水果】 题意： 给你一棵个点的树和条路径，每条路径都有一个权值。 有k组询问，每次询问给你一条路径和一个值。 问你被这条路径包含的所有路径中的第K小的路径的值 题解： 我用的是树上莫队+平衡树(或分块)的方法 平衡树的话是,分块的话就是 稍微口胡一下树上莫队： 把一颗树的欧拉序搞出来，对于查询的两点（假设入栈早）。 如果是一条链， 否则,,同时莫队是要加入 平衡树有什么用？ 我们看到题目中求第K大的值，就想到了用平衡树来维护值。 因为平衡树支持插入，删除和查找K大值，和莫队很配。 但其实分块更加优，分块能更好的和莫队配合。 因为分块的插入，查询，总的复...

题解 CF280D 【k-Maximum Subsequence Sum】 题意： 长度为的数列，支持两种操作： 1.修改某个位置的值 2.询问区间里选出至多个不相交的子段和的最大值。 一共有个操作 题解：线段树+堆 当k=1是答案就是最大子段和 当k=2是答案就有两种情况了： 1:最大子段和+不相交的次大子段和 2:最大子段和-最大子段和区间的最大子段和（其实就是把最大子段和分成两部分） 我们就想到像超级钢琴一样，选出一段,就加入, 比如我们在区间中找到最大子段和,那么我们就要把,的最大子段和已以及的最小子段和加入堆中 如果是最小子段和也差不多。在区间中找到最小子段和,那么我们就要把,的最小...

题解 P5471 【[NOI2019]弹跳】 做法：思维+动态开点线段树+分块 首先我们考虑最短路做法，发现边数是级别的。一维的情况我们能用线段树优化建边，但二维呢？反正我不会。 我们想到Dijkstra的思想，每次找到dis最小的点，并用这个点去更新其他点。 我们把矩形看成点，相当于每次找出dis最小的矩形，然后更新矩形中的点。 但一次性更新矩形中的全部点肯定不现实，我们就可以每次更新矩形中的一个点即可。 现在的问题就是如何找矩形中的一个点。发现有点难办啊。 一开始我想到是用树套树找点，结果被卡空间（QAQ），两只log的空间刚好被卡，舒适。 然后我们就考虑如何优化空间。大家都知道时间换空间...

题解 P5216 【DLS 采花】 题解： 考虑算每个数对答案的贡献。 第i个数的有贡献，当且仅当第i个数的约数出现在它后面。 假设第i个数有x个约数，那么有贡献的概率就是，有贡献的方案数就是总方案数概率。 为什么是呢?有个数，要选出那个数放在最前面，当然是。 代码： #include<bits/stdc++.h> using namespace std; #define next Next #define last Last #define int long long const int N=1e6+5; const int mod=998244353; int n,ans,a[...

题解 CF392D 【Three Arrays】 题解 首先肯定是要枚举一个的，我枚举的是（中的位置）。 但我们不能从小到大枚举，要从大到小枚举。 为什么呢？从大到小枚举的话，相当于是每次会多一些限制，这样比较好维护（如果是撤销限制，那不是很麻烦吗）。 考虑会多什么限制呢？ 就是那个数原来是在中被消灭的，现在不能在中被消灭了，那么就得在或中被消灭。 那到底是在中还是中呢？ 这就到了本题的关键地方了，我们把在中消灭的位置看成横坐标，在中消灭的位置看成纵坐标。这样的话，在二维平面中就有了一些点，我们要选一个横坐标和一个纵坐标，使得所有点要么横坐标，要么纵坐标。我们要求最小的。 怎么维护二维平面上的...

题解 P5490 【【模板】扫描线】 题解 看了怎么多题解，竟然没有一篇是下传标记的。 我来写一份常规的下传标记的做法。 我们需要维护区间最小值和最小值的个数 对于一个询问，如果区间最小值>0，那么返回区间长长度，否则说明区间有些地方是0，那么答案就是区间长度-最小值个数（长度） 然后就是普通线段树操作了，不需要标记用优化。 代码 #include<bits/stdc++.h> using namespace std; #define next Next #define last Last #define int long long const int N=1e6+5; in...

题解 CF1288E 【Messenger Simulator】 简单思维+数据结构 1.首先发现x的最小值一定是x或1（x出现过就为1，否则为x） 2.然后我们发现x最大值要么是x，要么是出现x 之前的 x所在位置。这个我们直接用线段树维护每个值的位子即可。相当于对于一个数，他会把比他大的数都加1。修改某个数的位子，就先消除这个数之前的+1，然后把他放到最前，在把后面的数加1。 代码： #include<bits/stdc++.h> using namespace std; #define next Next #define gc getchar //#define int lo...

一、tarjan 1.有向图缩点(强连通分量) 2.割点（根节点且有至少两个孩子 或 low[v]>=dfn[u]） if((fa==0&&son>1)||(fa!=0&&dfn[u]<=low[v]))cut[u]=true; 3.边双（两条边算一条，记一个vis标记一下有没有经过） P2860 [USACO06JAN]冗余路径Redundant Paths We Need More Bosses 求边双通常有两种方法：记住前驱节点，或是记住前驱边 。 注意重边问题，有些题只能记住前驱节点，有些题只能记住记住前驱边，不同的题不同对待。 记...