BST：二叉搜索树：中序遍历是从小到大的   动态维护一个有序序列

题目一：https://www.luogu.com.cn/problem/P16232   满足，且，输出有多少个，那么就是   所以答案是         题目二：https://www.luogu.com.cn/problem/P16233   如果有一盏灯，总次数为   如果有两盏灯，总次数为            如果有三盏灯，总次数为   如果有四盏灯，总次数为   手动模拟可以枚举到四盏灯，很显然一个结论是总次数等于    打表代码：   #include<bits/stdc++.h> using n...

 构造一棵含有个叶子节点的叉树，其中第个叶子节点带有权值，要求最小化，其中表示第个叶子节点的到根节点的距离。该问题被称为叉树     题目一：https://www.luogu.com.cn/problem/P1090   这是经典的入门题，就是二叉哈夫曼树；最小化，那么贪心的想法是不断合并权值最小的两个，这样使得小的大，大的小，用优先队列模拟。   因为有次合并操作，每次操作弹出与插入操作级别，所以时间复杂度为            题目二：https://www.luogu.com.cn/problem/P6033   题目一的加强版，必须使用的时间复杂度解决二叉哈夫曼树   使...

模板题目一：https://www.luogu.com.cn/problem/P8306      是字符串的最大可能长度，数组记录字符串的个数，是下标   const int N = 3000000 + 100; int son[N][62], cnt[N], idx = 0;  插入操作： 两处的位置有不同的效果，第一处记录的是所有字符串前缀的出现次数，而最后一处的记录的是所有完整字符串的出现次数   void insert(string s){  &...

题目一：https://www.luogu.com.cn/problem/P10589      使用权值线段树（因为我一开始用普通线段树超时了）   对每一个位置，求区间和中有多少个比大的数和比小的数      总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NU...

题目一：https://www.luogu.com.cn/problem/P1955  模板   注意离散化，下面给出两种离散化：  map<int, int> ma; int idx = 0; for(int i = 1; i <= n; i ++){     int op, x, y; cin >> x >>&n...

每次将最大值拆成两个数和，然后将除这两个数的其他所有数都加上，这里有是一个问题：一些数字需要加上，一些数字又不需要加上，然后多次操作下，一些数字加上的次数还不一样！不妨认为拆分成了和，这样相当于所有数字都需要加上，所以用一个变量记录所有数字一共需要加上的数。    所以可以用优先队列得到最大值，然后进行次操作即可：   void solve(){     int n, m, q, u, v, t; cin >> n >>&...

这道题目可以当作结论来记住了   相当于用的时间复杂度求：可以求出所有长度为的连续子数组里最小值的最大值        首先如果所有长度为的最小值中的最大值为，那么一定满足    我们可以求如果以当前为最小值的最大区间，那么需要找到向左第一个小于的值的位置，向右第一个小于的值的位置，那么区间的长度为，那么： ans[r[i] - l[i] - 1] = max(ans[r[i] - l[i] - 1], a[i]); 这样找到最长的区间，对于长度小于的区间的最大值一定大于等于，所以我只...

结论：设之前的位置为，然后删除位置坐标为的倍数的数，那么原来第个数的位置变为：    的意思是有多少个的倍数，所以直接减去     变形可以得到，意思是之前的位置等于现在的位置加上删除数字的个数    删除数字的个数等于，为什么是，因为如果，则算出来的一定不是的倍数，否则有可能是的倍数       故可以时间复杂度一步步算出:      总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long...

定义表示当前已经填了个数字，并且非数字为时的总方案数。显然的大小不会超过，最多个非零数字，所以不会超过   求区间的上等数字，等价于求区间的个数减去的个数   核心代码：   表示现在已经遍历到第几个位置了，因为数组将给一个个拆分了，此时从小到大对应的是的个位，十位，百位.....，然后遍历时就只能将从大到小枚举，这样先枚举高位然后枚举低位   当时说明数字已经枚举完，显然是一个升等数字，所以返回。   表示现在存在非数字的个数   ：枚举上限，因为中是先枚举高位，然后枚举低位；例如，如果现在最高位十位枚举的数字是，那么个位就只能枚举，不能超过原数，若十位枚举的数字是，那么个位就可以是。显然需...

很好的一道离散化题目   坐标范围在，那么二维数组肯定存不下，况且用二维前缀和枚举横纵坐标也是，超时   但是坐标个数最多只有个，也就是说不同的数最多也只有个，离散化后最关键的一个问题是如何枚举：正常的做法就是枚举横纵坐标，但是会超时，这里使用类似于双指针的方法来模拟：      总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::s...

求的最小值，当等于的中位数时，取得最小值。即将升序排列后，       题目一：https://www.luogu.com.cn/problem/P1862   显然只与总坐标有关，即求，将升序排列后，当时值最小      总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie...

看似背包，实则一点也不背包，物品的数量为，每一个物品的体积是，所以体积一样的物品可以累加   然后一共有m个背包，求背包的最小体积，但可惜，也不是二分   正确的思路是从二进制和贪心的方向去想：     二进制上，考虑每一位的贡献，而不是将打开   二进制从大到小去想，1是因为如果先考虑小的体积，那么很有可能导致大的体积放不进去了，导致背包不充分填充；2是因为我们是考虑二进制每一位，如果当前有剩余，那么可以传递到下一位......    第一步：将二进制从大到小排序   bool cmp(pair<int, int> a, pair<i...

对于二次函数：，     判断两者“独立”，即有无交点：            如果，那么如果，那么与无交点（题目保证同一组测试数据中）           如果，那么就用判断即可，其中，，     将依次按照升序或降序排列后，那么满足传递性：            如果与独立，与独立，其中，则与独立。具体证明过程略，分情况讨论      所以现在对于某一个...