link 非常直白的线段树题目 要注意负数的问题以及吮吸 #include<iostream> #include<cstring> #include<cstdio> #define int long long using namespace std; int tree[8000002]; int lazyre[8…

Jennie 用splay维护编号就可以了 如果我们要反转[l,r]，那么这个l，就是区间第l个数 然后splay的中序遍历就是整个区间， 那么显然的就是，我们只要找到第l个数就可以了 也就是所谓的按照排名找数。 找到之后，为了维护中序遍历，把l转到根，r转到l右边（也只能是右边了） 然后根r的左儿子打一个标记就可以了， 就像线段树一样，记得下传并…

JIsoo 首先根据期望dp搞出dp来， $f_{i}表示在到了第i个镜子还需要的期望天数$ 转移显然. $f_i=pi\times f{i+1}+(1-p_i)\times f_1$ 这也显然，并且没法递推hhhh 让我们从第二项开始化简式子 $\frac{1}{p_1\times p_2...p_i}+....+\frac{1}{p_i}$ 这…

Archie 这是一道主席树的题目 为什么这么说呢？因为根据推导，每个人的相对位置不变才是最优解 那么就涉及到每个人的位置位于1区间第几大了 当然每个人分开处理是可以的，不过一个权值线段树可以很好的帮助我们查询并且利用等差数列的性质来快速计算. #include<iostream> #include<cstdio> #inc…

扫描线和区间问题 用扫描线把静态二维问题转换成一维动态问题。 首先是最基本的形态 •给一个长为n的序列，有m次查询，每次查区间中<x的元素个数 看起来和扫描线有什么关系？？ 比如说一组数据，1，5，3，4，我们以下标为x轴，值为y轴，可以得到 假如我们要询问位于[2,3]中小于4的元素数量，我不就是想知道 这个矩形当中的点的数量嘛？ 这种思想…

Jennie 区间最长子序列的变体罢了 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; template<cl…