区间选点， 最大不相交区间数量

贪心方案：

根据右端点大小从小到大枚举所有区间
如果当前区间没有包含点，选改区间右端点为新的点，包含点则枚举下一个区间

证明：

设最优解点的个数为 $ans$，贪心解点个数为 $cnt$。
1. $ans \leq cnt$

贪心方案中每个区间包含一个点，所以是合法方案，大于等于最优解。
2. $ans \geq cnt$

根据贪心方案，根据右端点从小到大枚举所有区间，添加新的点时（从第二个点开始），当前区间左端点一定大于此前所有选的点，那么我们选择所有以此前所选点为右端点的区间，新选点所在区间与这些区间没交集。
即，根据贪心方案，当我们枚举到第 $i\ (i > 1)$ 个新点时，第一个以 $i$ 为右端点的当前区间，一定和以前 $i-1$ 个点为右端点的任一区间没有交集。
所以从贪心方案任意选择两个不同点，根据右端点从小到大枚举第一个以这两个点为右端点的区间，根据上面证明右端点大的区间一定和右端点小的区间没有交集，所以我们能选出 $cnt$ 个没有交集的区间，所以至少需要 $cnt$ 个点，贪心解小于等于最优解。

从 $\forall\ i\ (i \in (1, n])\ $ 第 $i$ 个区间与 前 $i-1$ 个区间没交集，推出 $n$ 个区间互相都没有交集。

区间分组

贪心方案：

根据左端点大小从小到大枚举所有区间
如果当前区间与所有已存组的区间有交集，新建一组，否则把当前区间加到任意合法组
由于根据左端点从小到大枚举，所以记录每组最后一个区间右端点即可

证明：

设最优解组数为 $ans$，贪心解组数为 $cnt$。
1. $ans \leq cnt$

贪心方案中每个组内互相无交集，所以是合法方案，大于等于最优解。
2. $ans \geq cnt$

根据贪心方案，当我们枚举到新建第 $cnt$ 个新组时，第 $cnt$ 组的当前区间左端点一定小于等于此前所有的组右端点最大的一个区间的右端点，左端点是从小到大枚举的，所以当前区间左端点一定大于等于这些区间的左端点，所以至少 $cnt$ 个区间有交集，根据贪心方案最后每组内互无交集，至少需要 $cnt$ 组，贪心解小于等于最优解。

容斥原理
题目描述
给定一nn个节点的无根树， 对每个点，计算距离小于等于kk的个数， 然后求出所有点距离小于等于kk的个数总和。

输入格式
第一行输入树的节点个数nn
接下来n−1n−1行，输入树上相连的两个端点uu，vv。

输出格式
一个数，所有节点距离小于等于kk的节点个数和

输入输出样例
输入
9 2
1 2
2 3
3 4
2 5
5 6
6 7
2 8
8 9
输出
45
说明/提示
1≤n≤2000001≤n≤200000;

0≤u,v≤n0≤u,v≤n;

目前能想到的解法，样例是过了

到父节点距离$k$的节点数等于距离他的子节点的距离$k-1$的节点数，
同时这里有重复计算，重复计算了子节点到父节点，父节点到其他点$k-2$距离的点，
减去重复的点同时又减多了，多减了父节点到子节点，距离子节点$k-3$的点,
如此往复然后规律就来了

$f[i][j]$表示到$\ i\ $节点刚好距离$\ j\ $的点个数
$f[father][k] = f[son][k - 1] - f[father][k - 2] + f[son][k - 3] ....f[][0]$

时间复杂度：$O(2nk^2)$ （每条边在一个循环里最多遍历两次，连接的两个节点每个遍历一次）
空间复杂度：$k$不能太大，$64mb$最多取$70$多

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, M = N << 1, K = 70;

int n, k;
int h[N], e[M], ne[M], idx;
int f[N][K];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i ++) f[i][0] = 1;

    for (int j = 1; j <= k; j ++)
        for (int i = 1; i <= n; i ++)
            for (int u = h[i]; ~u; u = ne[u])
                for (int p = 1, t = j; t; t --, p ++)
                {
                    if (p & 1)  f[i][j] += f[e[u]][t - 1];
                    else f[i][j] -= f[i][t - 1];
                }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= k; j ++)
            res += f[i][j];
    cout << res << endl;
    return 0;
}

纯练习
直接在线段树上做计数排序，数的范围太大要用动态开点
时间空间复杂度都是 O(nlog2m)O(nlog2m) n:1e5，m:1e9
786. 第k个数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k, idx;
struct Node
{
    int l, r;
    int size, val;
}tr[N * 30];

void pushup(int u)
{
    tr[u].size = 0;
    if (tr[u].l) tr[u].size = tr[tr[u].l].size;
    if (tr[u].r) tr[u].size += tr[tr[u].r].size;
}

void insert(int p, int l, int r, int x)
{
    if (l == r)
    {
        if (tr[p].l) tr[p].size ++;
        else tr[p] = {l, r, 1, x};
    }
    else    
    {
        int mid = l + r >> 1;
        if (x <= mid) 
        {
            if (!tr[p].l) tr[p].l = ++ idx;
            insert(tr[p].l, l, mid, x);
        }
        if (x > mid)
        {
            if (!tr[p].r) tr[p].r = ++ idx;
            insert(tr[p].r, mid + 1, r, x);
        }
        pushup(p);
    }
}

int find(int p, int k)
{
    if (tr[p].l == tr[p].r) return tr[p].val;

    if (tr[p].l)
    {
        if (tr[tr[p].l].size >= k) return find(tr[p].l, k);
        else return find(tr[p].r, k - tr[tr[p].l].size);
    }

    if (tr[p].r)
        return find(tr[p].r, k);

}

int main()
{
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i ++)
    {
        int x;
        scanf("%d", &x);
        insert(0, 1, 1e9, x);   
    }

    printf("%d\n", find(0, k));
    return 0;
}

约束类问题
变量就一个，其他的所有值都能有这一个变量和常数表示，类似于递推的问题
设变量，求函数的极值
不等关系，列不等式，求解集关系

不会，根本不会，只能看完官方题解加代码后会一点点。
之前寒假每日一题1443. 拍照做过两个值的递推，枚举第一个值后递推出每个值，然后判断合不合法就可以了，这题枚举前两个值才能递推，根据数据范围显然不行。

我又懂了，有前两个值就能递推出所有值，所以变量只有两个，用这两个变量就能表示所有值，再根据题意要求$A_i \geq 0$能列出$n + 2$个不等式，判断所有不等式解集有无交集。

规律：
$$ \begin{cases} a_1 = a_1 \\\ a_2 = a_2 \\\ a_3 = S_1 - a_1 - a_2 \\\ a_4 = S_2 - a_2 - a_3 = S_2 - S_1 + a_1 \\\ a_5 = S_3 - a_3 - a_4 = S_3 - S_2 + a_2 \\\ a_6 = S_4 - a_4 - a_5 = S_4 - S_3 + a_3 = S_4 - S_3 + S_1 - a_1 - a_2 \\\ a_7 = S_5 - a_5 - a_6 = S_5 - S_4 + a_4 = S_5 - S_4 + S_2 - S_1 + a_1 \\\ . \\\ . \\\ . \\\ a_{n+2} = S_{n} - S_{n-1} + a_{n-1} \ 取决于n-1模3的余数 \end{cases} $$

找规律分类，列不等式，判断满不满足约束，简单复读一下官方题解:

假设$A_1 = a, A_ 2 = b$，可以根据$S_i$的值递推出所有的$A_i$，此时根据规律可以发现，$A_i$根据$i$除以3的余数分成三类，$x_i$是关于$S_i$的函数（即能用$S_i$表示）

$$ \begin{cases} A_i = x_i + a & \(i=1, 4, 7…\) \\\ A_i = x_i + b & \(i=2, 5, 8…\) \\\ A_i = x_i - a - b & \(i= 3, 6, 9…\) \\ \end{cases} $$
令$a = b = 0$，可以求出所有的$x_i$，题意要求$A_i \geq 0$，上述方程转化成下列不等式
$$ \begin{cases} a \geq -x_i & \(i=1, 4, 7…\) \\\ b \geq -x_i & \(i=2, 5, 8…\) \\\ a + b \leq x_i & \(i= 3, 6, 9…\) \\ \end{cases} $$
找出$a,b$的最小值（$-x_i$的最大值，即第一二类$x_i$的最小值）与第三类的$x_i$的最小值比较，满足即可得到一组解，不满足即无解

为什么acwing里，公式块儿里公式换行要用三个反斜杠，外面教程里都是两个啊

AcWing 104. 货仓选址
AcWing 1536. 均分纸牌
AcWing 1843. 圆形牛棚
AcWing 122. 糖果传递
AcWing 105. 七夕祭

随机断环为链,箭头方向固定顺时针方向，正负号表示传递方向
ai 最优解第i个需向顺时针下一个传递的数量
si 随机断环后实际传递
断了n这条边，即所有边传递数量减去an
S1 = a1 - an       
s2 = a2 - an
.
.
sn-1 = an-1 - an
sn = an - an

设边k为最优解，ak = 0，边权为0
中位数为最优解，Sk = ak - an = -an  
-an为S1到Sn的中位数，ak也就是a1到an的中位数，0是最优分配中的中位数

0在最优中也是中位数，即最优链中正负边数都不会过半

破案了：如果有多余一半的正权边，把最小的正权边ak斩断变成0，会比当前的解更优
斩断前：|A(正)| + |A(非正)| = A（正）- A（非正）
斩断后：A(正)- (正权边数) * Ak + （非正边数）* Ak - A（非正）
      = A（正）- A（非正）- （正权边数 - 非正边数）* Ak   
      比斩断 前更小

所以：正权边数 <= 非正权边数
同理可证：负权边数 <= 非负权边数



an  a1      a2 ....  ak ...    an-1
0  a1 - an  a2 - an  0-an  ... an-1 - an

最优解，0中位数，正负边数都不会过半

总结：瞎想只有死路一条，跪在巨人的肩膀上当复读机才是正途

雨女无瓜：
AcWing 1913. 公平摄影
AcWing 99. 激光炸弹
AcWing 100. IncDec序列
AcWing 101. 最高的牛