caioj 1125
二分图最小点覆盖模板题，同样使用最大流dinic做

BZOJ 2243
这题就是caioj 1102树上版。
所以我们树剖然后线段树维护

• $lcol$：区间左端点的颜色
• $rcol$：区间右端点的颜色
• $cnt$：区间线段的条数

然后合并区间的时候如果中间颜色相同，要$cnt-1$
查询同理，如果左右区间都更新了，则要判断中间颜色

之后树剖的合并就比较麻烦。要分两边来存上一个区间端点颜色是什么，然后最后$u$到$v$的修改也要讨论，这个仔细想想就行，但是容易写错，建议画一下，详情看代码，不太好讲

注意树往深的方向是右方向，浅的方向是左方向，而且$pushdown$记得子节点要传$lazy$

caioj 1102
(本题为bzoj 2243弱化版)
线段树维护三个值：

• $lcol$：区间左端点的颜色
• $rcol$：区间右端点的颜色
• $cnt$：区间线段的条数

然后合并区间的时候如果中间颜色相同，要$cnt-1$
查询同理，如果左右区间都更新了，则要判断中间颜色
或者把所有区间先找出来再一一合并

模板及讲解

1、进制转换
整数：

• 十进制转$n$进制：用短除法。不断地除以$n$，倒序取余数，直到十进制数为0
• $n$进制转十进制：按位加权乘积和，第一位权为$n^0$, 第二位权为$n^1$，依此类推

小数：

• 十进制转$n$进制：不断地乘$n$，正序取整数部分，直到无整数部分。
• $n$进制转十进制：按位加权乘积和，小数位第一位权为$n^{-1}$, 小数位第二位权为$n^{-2}$，依此类推

2、原码，反码，补码
负数：

• 原码：一个二进制数，其最前一为为符号位，1为负，0为正
• 反码：原码各位取反(除符号位)
• 补码：反码$+1$

正数：原码 = 反码 = 补码

3、二叉树遍历

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根

4、逻辑符号

• 非：$¬$
• 与(交)：$∧$
• 或(并)：$∨$
• 异或：$⊕$

5、前缀、中缀、后缀表达式

• 中缀表达式：$(3+4) \times 5 - 6$
• 前缀表达式：$- \times + 3 4 5 6$，从右往左扫描栈处理
• 后缀表达式：$3 4 + 5 \times 6 -$，从左往右扫描栈处理

spoj QTREE3
树剖，然后线段树维护区间第一个出现的黑点。由于单点修改所以很简单了
(注意！树剖的$u,p_u,np_u$的意义要弄清楚！树剖时重点检查对象)

spoj QTREE2
把一条路径根据$LCA$拆成两条链，然后判断第$k$个点在哪条链上即可
注意求LCA的时候要判断深度大小，以及树上的路径权值和不要误认为是距离了

STL

STL的容器都为左闭右开区间$[begin(), end())$

vector

• size()：查询$vector$中元素的个数。
• [index]：直接访问$vector$数组第$index$个元素。
• push_back(x)：把$x$放在$vector$的表尾。
• reverse(begin(), end())：把$begin()$到$end()$之间的元素翻转
• reserve()：手动调整$capacity$
• rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

set

• count()：查询$set$中元素的个数。
• insert(x)：把$x$插入$set$.
• lower_bound(x)：找到第一个大于等于$x$的元素(找不到返回$end()$)。
• erase(x)：删除$x$迭代器所指向元素(不能删去$begin()$)。
• set<type>::iterator：声明一个迭代器，访问元素使用data->x来访问，类似指针
• rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

map

• rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

string

• substr(int a, int len)：把$[a,a+len]$提取出来返回值为$string$
• length()：得出字符串长度
• assign()：给string赋值，具体看使用
• rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

注意所有end()调用即会出错。

pbds

rope

P3835 【模板】可持久化平衡树
模板：可持久化平衡树

主要用lower_bound和insert(pos, x)
注意复制方法new rope<int >(*seq[v]);

// luogu-judger-enable-o2
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/rope>
using namespace __gnu_cxx;

namespace flyinthesky {

    const int MAXN = 500000 + 5;

    rope<int > *seq[MAXN]; // 指针方便复制
    int Q;
    inline int rd() {
        register int data = 0, w = 1;
        register char ch = 0;
        while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
        if (ch == '-') w = -1 , ch = getchar();
        while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
        return w * data;
    } 

    void clean() {
    }
    int solve() {

        clean();
        cin >> Q;
        seq[0] = new rope<int >;
        for (int i = 1; i <= Q; ++i) {
            int v, op, x; v = rd(), op = rd(), x = rd();
            seq[i] = new rope<int >(*seq[v]);
            if (op == 1) {
                seq[i]->insert(lower_bound(seq[i]->begin(), seq[i]->end(), x) - seq[i]->begin(), x);
            }
            if (op == 2) {
                auto it = lower_bound(seq[i]->begin(), seq[i]->end(), x);
                if (it != seq[i]->end() && *it == x) seq[i]->erase(it - seq[i]->begin(), 1);
            }
            if (op == 3) {
                printf("%d\n", lower_bound(seq[i]->begin(), seq[i]->end(), x) - seq[i]->begin() + 1);
            }
            if (op == 4) {
                printf("%d\n", *(seq[i]->begin() + x - 1));
            }
            if (op == 5) {
                auto it = upper_bound(seq[i]->begin(), seq[i]->end(), x);
                --it;
                printf("%d\n", (int)*it);
            }
            if (op == 6) {
                auto it = upper_bound(seq[i]->begin(), seq[i]->end(), x);
                printf("%d\n", (int)*it);
            }
        }

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}

BZOJ 2028
luogu免权限地址
Set维护不相交区间，lower_bound求前后与当前区间最近的区间，检查是否重合，重合即删除，直到不重合为止。
注意set.lower_bound()如果找不到就会返回set.end()

线段树做法：
裸模板，维护区间增加区间最小值，但是常数大容易T

二分+前缀和做法：
每次二分一个通过申请的个数，然后暴力前缀和判断，复杂度与线段树一样，但是常数小

25分水法：
直接模拟，增加$q$直接暴力把堆中的元素取出来加完放进去

65分水法：
直接按照题意模拟，但是堆里面存当前蚯蚓长度与 增加量$q$ 的差值(具体看代码),来避免每次使蚯蚓增加$q$.

90分水法：
发现很多数据$q=0$，那么等于蚯蚓不会再加了，考虑单调性。
用三个队列$q_1,q_2,q_3$，分别代表原始数据，切分第一部分，切分第二部分。
然后每次从三个队列里取最大值出来切，然后结果分别放进$q_2,q_3$。
这样做是对的，因为这样做数据是单调递减的，前面切的两部分一定比后面切的两部分分别大于。
然后加上65分的程序分段，这样就有90分了，注意分段程序千万别打错，不然白打前65分。

100分正解：
根据上一个90分做法，我们被暗示了——单调性。
$q≠0$也是单调的吗？是的。
我们通过反证可以知道：设$a_i$为当前被切割的蚯蚓的原长，$a_j$为$a_i$之前隔了$n$时段被切割的蚯蚓的原长
那么假设不单调，即出现：
$a_i \times p + n \times q \leq (a_j + n \times q) \times p$
那么就是
$a_i \times p + n \times q \leq a_j \times p + n \times q \times p$
因为$a_j \leq a_i, 0 < p < 1$，那么
$a_i \times p + n \times q > a_j \times p + n \times q \times p$成立
与之前的假设矛盾，因此是单调的
NOIP的部分分都是在暗示正解的方向，不过以后或者其他比赛可能回不会。所以尽可能往部分分想会暗示什么，但是也不要完全依赖部分分提示。
上述算法虽然难以证明，但是在想到90分做法以后，联想到$q≠0$，那就可以作一个假设，之后用暴力对拍即可验证正确性(你的暴力肯定要对)。

下面代码给出了3个分数档次(65,90,100)的代码：