不在沉默中躺平，就在喧嚣中躺平。
但谁说人一定要躺平？我要 work work work work work work work work 勤劳又勇敢的 XSC062 为了 OI 的关键杂题集 她作出了巨大的贡献 巨大的牺牲 巨大的 carry 无敌了 无敌了 
[USACO23JAN] Moo Route G
https://www.luogu.com.cn/problem/P9018
关键词：由小推大 思维
希望大家不要和我一样忽略了重要条件：终点也是 \(0\)。这意味着每个点都会被左右成对地经过，那么不妨令 \(A_i\gets \frac 2{A_i}\)。
观察到给了 \(N=2\) 的一档分，考虑该情况。
若 \(A_1> A_2\)：
只要不拆开一组，箭头排列顺序任意。显然方案数为 \({A_1}\choose {A_2}\)。此时最优策略为……
|---------> <---------| |---------> <---------| |---------> <---------| |----> <----| |----> <----| =========== 0 1 2Otherwise：
此时最优策略为……
|----------> <----| |----> <----| |----> <---------| |---------> <---------| =========== 0 1 2相似地，只要不拆开一组，箭头排列顺序任意，可以注意到除了第一个，每个长
|--->的前面一定是一个长<---|，那么问题转化为选择 \(A_1-1\) 个短<---|拉长，方案数为 \({A_2-1}\choose{A_1-1}\)。
进一步，考虑 \(N=3\) 的情况。若已知子问题 \(0\to1\to2\) 的方案和子问题 \(1\to2\to3\) 的方案，可以直接乘起来合并。为什么呢？
二者经过 \(2\) 的次数相等；在子问题 \(0\to1\to2\) 中，\(1\to2\) 的下一步一定是 \(2\to 1\)；我们把该过程替换为子问题 \(1\to 2\to 3\) 中对应的一段 \(1\to2\to\cdots\to2\to1\) 的路径即可。
那么两两合并起来，可以得到最终答案为 \(\prod\limits_{i=1}^{n-1}\begin{cases}{\binom{A_i}{A_{i+1}}}&A_i>A_{i+1}\\{\binom{A_{i+1}-1}{A_i-1}}&\text{otherwise}\end{cases}\)。
#include <bits/stdc++.h>
const int lim = 5e5;
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], a[i] /= 2;
std::vector<long long> inv(lim + 1), fac(lim + 1);
auto qkp = [&](long long x, int y) {
long long res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[0] = fac[0] = 1ll;
for (int i = 1; i <= lim; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[lim] = qkp(fac[lim], mod - 2);
for (int i = lim - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
long long res = 1ll;
for (int i = 1; i < n; ++i)
if (a[i] > a[i + 1])
(res *= C(a[i], a[i + 1])) %= mod;
else
(res *= C(a[i + 1] - 1, a[i] - 1)) %= mod;
std::cout << res << '\n';
return 0;
}[GDKOI2024 普及组] 正方形扩展
https://www.luogu.com.cn/problem/P10078
关键词：分类讨论 扫描线
理论上看懂了就是弱智题，可惜看不懂。
就是说，一个点如果被染了某种颜色，并且以它为中心的边长为 \(2\) 的正方形中没有其他颜色的点，就把这个正方形里的点都染成这个颜色，问每个颜色面积是否能达到无穷大。
考虑无法达到无穷大的原因，一定是因为向四个方向都无法延伸到无穷远。以右边为例，考虑点 \(i\) 什么时候不能在 \(x\) 轴正方向上延伸到无穷远：
对于 \(\forall \, j,x_j\le x_i\)，\(j\) 不会对 \(i\) 向右的延伸带来任何影响——所有点的延伸速度相同。
对于 \(x_j>x_i\) 且 \(y_j=y_i\)，\(j\) 可以堵住 \(i\)。
这时候不免产生疑问：\(i\) 不能从上下「翻越」过 \(j\) 的统治吗？
显而易见地，由于延伸速度相同，\(i\) 在某时刻能够在 \(y\) 轴上到达的高度，\(j\) 也能达到，所以 \(j\) 能够把 \(i\) 堵死，参见题面中给出的例子。
对于 \(x_j>x_i\) 且 \(y_j \ne y_i\)，由上所述，\(j\) 在 \(y\) 轴下 / 上方向无法追上 \(i\)，\(i\) 可以从该方向越过 \(j\)，在 \(x\) 轴正方向上延伸到无穷远；但 \(j\) 在自己所在的一侧（上 / 下）可以堵住 \(i\)。
对于 \(x_j,x_k>x_i\) 且 \((y_j-y_i)(y_k-y_i)<0\)（即二者分居 \(i\) 点上下），\(j\) 和 \(k\) 可以在两个方向分别拦截住 \(i\)。
此时可能有疑问：\(i\) 可不可以先越过 \(j\) ，再越过 \(k\) 呢？答案是否定的。由上，\(j\) 和 \(k\) 会分别在 \(y\) 轴自身对应方向上堵住 \(i\)，在越过其中之一后无法从这一侧越过另一个点，所以 \(i\) 会被两个点合作堵死。
由此我们总结出，\(i\) 能在 \(x\) 轴正方向被拦截，当且仅当：
- 存在 \(x_j>x_i\) 且 \(y_j=y_i\)；
- 抑或，存在 \(x_j,x_k>x_i\) 且 \(y_j<y_i,y_k>y_i\)。
那么可以从四个方向分别用扫描线求解。鉴于和实际坐标数值没有什么直接关系，可以离散化后树状数组以避免被卡常。
金鱼草
http://222.180.160.110:61235/contest/6051/problem/4
给定 \(n\) 个区间 \([l,r]\) 满足 \(r\le m\)，给出 \(q\) 个询问，每次询问 \([L,R]\) 是否能被表示为若干 \([l,r]\) 的 OR（并）。
\(n,m,q\le 5\times 10^5\)。
关键词：扫描线 线段树维护特殊数据
小清新数据结构题。题目所求等价于 check 满足 \(l\ge L\land r\le R\) 的所有区间是否能够覆盖 \([L,R]\)。
在考虑是不是能够用数据结构直接完成任务时，发现线段树可以维护「一段连续左端点中是否能够完整覆盖一段数」，具体地，维护每一段区间能够最远到达的右端点 \(rv\)（那么显然从区间左端点到 \(rv\) 都能被连续覆盖），区间内最靠右的没有被覆盖到的点 \(p\)，和表示区间是否能被完整覆盖的标记 \(flag\)。\(rv\) 是易维护的；而 \(flag=0\) 当且仅当：
左儿子的 \(flag=0\)。
此时若右儿子 \(flag=0\)，那么当前结点 \(p\) 可赋为右儿子的 \(p\)；否则，\(p\) 赋为左儿子的 \(p\)。
左儿子的 \(flag=1\)，但右儿子 \(flag = 0\)，且左儿子的 \(rv\)够不到右儿子的 \(p\)。
此时当前结点的 \(p\) 仍为右儿子的 \(p\)，因为我们只在意最远的没有被覆盖到的点。
容易发现如果我们在树上询问 \([L,R]\) 中所有左端点的 \(flag\)（询问方法和 pushup 是类似的），无法保证参与覆盖的 \(r\le R\)。故离线下来扫描线，从左到右枚举每个 \(i\) 作为 \(R\) 的情况，把所有 \([l,i]\) 插入线段树，对于每个询问 \([L,i]\) 即可在树上直接查询答案。
bb：据说是 d1t2 水平，但我居然 1min 不到把解法大概胡出来了？希望 CQOI2025 也这么胡（双关
bb：似乎是一个全新的不需要区间修改的做法
#include <bits/stdc++.h>
const int maxn = 5e5 + 5;
struct _ {
bool flag;
int l, r, rv, p;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].rv = std::max(t[lt].rv, t[rt].rv);
if (!t[lt].flag) {
t[p].flag = 0;
if (!t[rt].flag && t[lt].rv < t[rt].p)
t[p].p = t[rt].p;
else
t[p].p = t[lt].p;
}
else if (!t[rt].flag && t[lt].rv < t[rt].p)
t[p].flag = 0, t[p].p = t[rt].p;
else
t[p].flag = 1, t[p].p = 0;
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = t[p].p = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void add(int p, int x, int v) {
if(t[p].l == t[p].r) {
t[p].flag = 1, t[p].p = 0;
t[p].rv = std::max(t[p].rv, v);
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
add(lt, x, v);
else
add(rt, x, v);
pushup(p);
return;
}
_ ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p];
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid)
return ask(lt, l, r);
if (l > mid)
return ask(rt, l, r);
auto ls(ask(lt, l, r)), rs(ask(rt, l, r));
if (!ls.flag) {
if (!rs.flag && ls.rv < rs.p)
ls.p = rs.p;
}
else if (!rs.flag && ls.rv < rs.p)
ls.flag = 0, ls.p = rs.p;
ls.rv = std::max(ls.rv, rs.rv);
return ls;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("snapdragon.in", "r", stdin);
std::freopen("snapdragon.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, q;
std::cin >> m >> n >> q;
bld(1, 1, m);
std::vector<std::vector<int> > t(m + 1);
for (int i = 1, l, r; i <= n; ++i) {
std::cin >> l >> r;
t[r].push_back(l);
}
std::vector<int> res(q + 1);
std::vector<std::vector<std::pair<int, int> > > tq(m + 1);
for (int i = 1, l, r; i <= q; ++i) {
std::cin >> l >> r;
tq[r].emplace_back(l, i);
}
for (int i = 1; i <= m; ++i) {
for (auto l : t[i])
add(1, l, i);
for (auto [l, id] : tq[i])
res[id] = ask(1, l, i).flag;
}
for (int i = 1; i <= q; ++i)
std::cout << (res[i] ? "YES" : "NO") << '\n';
return 0;
}