题目链接：https://vjudge.net/contest/332656#problem/I   题目大意： 小明需要安排和基友开黑和和女神约会的时间。这两个时间总是一段连续的时间，小明总是会找最早的时间来开始这些事。当有基友找他开黑的时候，他会先在时间表里找最早的连续时间，如果有，就开黑，没有就不开黑。当有女神和他约会，他先在时间表里找最早的连续时间，如果有就约会，没有他会先不考虑和基友开黑，先和女神约会，如果有时间就约会。 思路： 因为涉及到基友和女神，那线段树里就需要维护两种连续区间，分别为女神的和***丝的，区间维护三个，左边最大连续区间，右边最大连续区间，和总的最大连续...

题目链接：https://vjudge.net/problem/POJ-3667   题目大意：n个连续的房间m个操作。操作分两种， 第一种以1 x形式给出，找到最左的能连续容下x个人的连续房间，并输出左端点的编号，如果找不到就输出0. 第二种以2 l x的形式给出，表示以l为起点的x个房间都清空。   思路： 采用线段树去维护最大连续区间。具体的讲解可以看：https://www.cnblogs.com/lonely-wind-/p/11667471.html   1 #include <math.h> 2 #include <stdio.h...

题目链接：https://vjudge.net/contest/332656#problem/H    题意： n个花瓶，m个操作，花瓶里面有的有花，有的是空的。 1 x y 表示从第x个位置开始查y多花，若一朵花也插不上输出"Can not put any one."，反之输出插花的左位置和右位置。 2 操作是清除区间[a,b]的花。并输出清除了多少花。   思路：线段树维护区间，然后每次二分查找满足要求的第一个位置。   1 #include <math.h> 2 #include <stdio.h> 3 #i...

C. White Sheet   一道基础的几何题  给定三个矩形的左下角坐标和右上角坐标，第一块是白色矩形，第二第三都是黑色矩形，问白色矩形是否被黑色矩形完全覆盖。思路就是根据点判断分类讨论。   1、如果白色矩形的四个点没有全部被覆盖了   那么直接输出“NO” 2、如果白色矩形的四个点都被覆盖了，那么就再判断下黑色的矩形有没有交集   1 #include <math.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #i...

题目链接：https://vjudge.net/contest/332656#problem/F   题意： 给出一个有向树，初始所有节点为-1.有两种操作，一种为(T,x,y)，表示将x节点的所有子树中的节点变为y，另一种为(C,x)，为求x节点的值   思路： 采用 dfs序 使得每个结点以及它的孩子都是连续的！    1 #include <math.h> 2 #include <stdio.h> 3 #include <iostream> 4 #include <algorithm> 5 #inc...

题目链接：https://vjudge.net/contest/332656#problem/G   题意： 给你三种操作，三种输出方式： 1.让l~r区间的所有值加c； 2.让l~r区间的所有值乘c； 3.让l~r区间的所有值变成c； 4.让l~r区间的所有值都先求p（1~3）次方，然后求和输出。   思路： 这道题坑在有三种询问：set , add , mul。所以lazy标记要有三个，如果三个标记同时出现的处理方法——当更新set操作时，就把add标记和mul标记全部取消；当更新mul操作时，如果当前节点add标记存在，就把add标记改为：add * mul。这样的话...

题目链接：https://codeforces.com/contest/1234/problem/C   题意： 可以参见luogu https://www.luogu.org/problem/CF1234C   思路： 因为它的管子是可以旋转的，所以 其实 1、2号管子其实都是一样的，不妨让它们都是 1 同理 3、4、5、6管子也是一样的，不妨让它们是2   然后我们再来考虑一下所有可能出现的情况 1、如果前面是 管子1 那么就直接往前走 2、如果前面是 管子2 并且它的下方（上方）也是 管子2 ，那么就会走到 下层 （上层） 3、如果前面是 管子2 并且它的下方（...

题目链接：https://codeforces.com/contest/1234/problem/D   题意： 给一个字符串s，存在两种操作 操作1：将某一位的字符改成给定的一个字符 操作2：询问一段区间内不同字符的个数   思路： 线段树维护各个区间的字符。然后查询的时候新开一个 数组t 去记录不同的字符 最后统计 t中字符的个数就可以了   不知道为什么我用set 和 string 就TLE 了   1 #include <math.h> 2 #include <stdio.h> 3 #include <iostr...

题目链接：https://vjudge.net/contest/332656#problem/E   思路： 稍微改下线段树求连续区间的代码就好了   具体的解释还是看代码注释吧   1 #include <math.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <string> 7 #include <strin...

题目链接：https://vjudge.net/contest/332656#problem/D   思路：因为根号运算n衰减的很快，所以在极少数的操作内它就会变成1，所以当整个区间内的值都变成1时直接返回，反之暴力更新叶子结点就好   1 #include <math.h> 2 #include <stdio.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <string> 6 #include <string.h&gt...

权值线段树 其实权值线段树在学习主席树的时候我就提到过这个东西。 权值线段树和普通线段树之间区别就是在于 它存储的是 区间内数的个数   所以用这种数据结构我们可以求解一个 完整区间的第k大 ，要注意和主席树的区别。 主席树更加强大！！   学了主席树反过来学权值线段树超简单   直接上例题：黑匣子https://www.luogu.org/problemnew/show/P1801     1 #include <stdio.h> 2 #include <iostream> 3 #include <algorithm> 4...

浅谈可持久化线段树--主席树 权值线段树 权值线段树和普通线段树不一样的地方就是在于 它的结点存储的是区间内数的个数 这个线段树的好处就在于我们可以根据 左子树 和 右子树 的大小从而进行 查找某个数的排名 或者 查找排名为rk的数   可持久化的含义 可持久数据结构主要指的是我们可以查询历史版本的情况并支持插入，利用使用之前历史版本的数据结构来减少对空间的消耗（能够对历史进行修改的是函数式）。    主席树的建树过程： 最开始的时候就是一个空树       然后我们再插入一个元素3     再加入一个元素 1       模版一 ：求区间第...

区间的操作最主要的地方就是把 split 操作从按权值分裂 改成了 按大小分裂   我们把 大小 == k 放在一棵树，然后其余的放在另一棵树   1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <random> 5 6 const int maxn = 1e5 + 10; 7 8 struct Node { 9 int l,r; 10 int val,key; 11 ...

其实二叉平衡树就是通过各种奇异的操作从而维持二叉树的平衡 fhq Treap特殊就特殊在它并没有像其他性能非常优越的平衡二叉树一样是通过旋转从而实现二叉树的平衡   fhq Treap的核心操作其实就两个 ----  分裂 和 合并   分裂 分裂就是把一棵二叉平衡树 分成两个二叉平衡树， 左边的二叉平衡树的所有点的权值都 < 右边二叉平衡树所有点的权值 分裂的方式有两种 ：  1、 按值分裂 2、按排名分裂   这里先讲按值分裂： 如果我们遍历到的当前这个结点的值 <= val ，那么我们就把这个结点放入左边的树 。 如果当前这个结点的值 > va...