求多个矩形的面积并

沿 $x$ 轴扫描，用数据结构维护 $y$

这题用到的数据结构很有意思

但是这道题目存在一个特殊的性质：每个数不会减到负，所以问题就简单了

下面是线段树节点合并

1
2
3
4
5

// s 是当前节点
s.sum = s.t
    ? raw[s.r] - raw[s.l-1]
    : (s.l == s.r ? 0 : T[ls].sum + T[rs].sum);

主要是记一个结论

这样，维护区间修改 $\gcd$ 查询就非常方便

注意 $\gcd$ 的写法

1
2
3
4
5

ll gcd(ll x, ll y){
    return x && y
        ? gcd(y, x%y)
        : std::max(std::abs(x),std::abs(y));
}

¶ 知识点

• P Problem: 对于任意的输入规模n，问题都可以在n的多项式时间内得到解决；
• NP(Non-deterministic Polynomial) Problem: 可以在多项式的时间里验证一个解的问题；
• NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件 (1)是一个NP问题 (2)所有的NP问题都可以约化到它
• NP-Hard Problem: 满足NPC问题的第二条，但不一定要满足第一条

（ AB ）属于 NP 类问题。

• 存在一个 P 类问题
• 任何一个 P 类问题
• 任何一个不属于 P 类的问题
• 任何一个在（输入规模的）指数时间内能够解决的问题

主定理

考虑 $A(n)=n^{\log_b a}$ 和 $f(n)$ 的大小

• $f(n)<A(n)$ ， $O(A(n))$
• $f(n)=A(n)\log^k n$ ， $O(A(n)\log^{k+1}n)$
• $f(n)>A(n),\exist\;c<1, af(n/b)<cf(n)$ ， $O(f(n))$

给定长为 $n\le 2\times 10^5$ 的序列，你需要将其中 $k$ 个节点染色，满足 $m\le 10^5$ 组条件：$[l_i, r_i]$ 中有且仅有一个节点被染色。

最大化 $k$

题面，数据

「Link」

令左边房子为 $l_i, r_i$ ，正在考虑右边 $L,R$ 房子的答案

求出第一个 $i$ 满足 $r_i > L$

求出第一个 $j$ 满足 $l_j > R$

$j-i$ 即为贡献

因为不能向上走，所以可以一行一行考虑

$f_{i,j}$　表示从 $(i,j)$ 走到最后一行的期望步数，$f_{n,j}=0$

矩阵大概是这样的，需要优化求解

「Link」

首先观察炮的攻击范围，左右上下完全对称

也就是说，A 打不到 B 和 B 打不到 A 是等价的，于是就考虑左边和上面

一行一行地考虑，正在考虑第 $i$ 行

一行内部炮冲突的问题是容易解决的

「Link」

一道 trivial 的 DP

$w\times h$ 的纸张，每次能沿横或纵切一刀，最先切出 $1\times1$ 的人赢

$2\le w,h\le 200$

一行棋盘，若干个棋子，初始状态给出，每次可将棋子移到右侧第一个空格（棋子与空格不一定相邻 如：1101->1011/0111），不能移者输。