2020-10-16发表2020-12-27更新OI笔记22 分钟读完 (大约3309个字)

考前的小知识积累

快考试了，整理一下最近学到的细碎的东西。东西很杂，也有一些叫不上名字来，简单写写吧……

max+ 矩阵乘法

定义一类新矩阵乘法：
$$ C= A * B\Leftrightarrow C_{i,j}=\max\limits_{i,j,k}A_{i,k}+B_{k,j} $$ 为矩阵的 max+ 乘法。注意到这类乘法是满足结合律的，因此可以快速幂优化。这类乘法的本质类似于一轮 Floyd 传递闭包。

max+ 卷积

定义一类新的序列卷积：
$$ C=A*B\Leftrightarrow C_k=\max\limits_{i+j=k}A_i+B_j $$ 这类卷积很难做到低于 $O(n^2)$ 的复杂度内计算，但是如果 $A,B$ 都是离散意义下的凸函数的话，可以做到 $O(n\log n)$ 计算，方法如下：

把序列 $A,B$ 分别排序后差分，把得到的增量合并到一个序列中降序排序，这会得到一个长度为 $2n-2$ 的新序列，记为 $\text{d}$。注意到必然有 $C_0=A_0+B_0$，我们下一步需要按从大到小的顺序把增量加进去，即有 $C_1=C_0+\text{d}_0, C_i=C_{i-1}+\text{d}_{i - 1}$，于是就还原出了卷积后的结果 $C$，时间复杂度只有排序的 $O(n\log n)$。

这种做法的正确性在于：对于凸函数而言，增量 $\text{d}$ 的可取范围与其大小是相应变化的。那么如果做凹函数的 min+ 卷积的时候，也可以适用类似的做法。

斜率优化

有一种普适性的在亚线性时间复杂度内，解决一类距离最值问题的方法，通俗的叫法好像叫做斜率优化。

这类问题的一般模型是：定义一类新的距离 $\text{dist}(i,j)=A_i+B_j+C_iD_j$，求 $\min\limits_{i,j}\text{dist}(i,j)$。注意到关于 $i, j$ 的下标运算是二次的，因此无法拆开来简单维护。

考虑枚举 $i$，转化为求如下式的值：$p + \min\limits_{1\le j\le n} B_j+kD_j$，设有 $l_j=B_j+kD_j$，得到 $B_j=-kD_j+l_j$，这是一条过定点 $(D_j, B_j)$，斜率为 $-k$ 的直线，而我们要最小化的东西是这条直线的截距 $l_j$。

那么现在等价于给出一堆点 $(D_1,B_1),(D_2,B_2),…,(D_n,B_n)$ 和一个斜率 $-k$，让我们求一条直线使得截距最小。显然，所求点必然在这些点形成的下凸壳上，那么维护出下凸壳二分即可。
有时斜率给出的性质特殊，则可以单调维护；当点的选取范围有要求时，可以结合单调栈 / 线段树。

给出一个示例：求 $\min\limits_{i,j}a_i+b_j+(i-j)^2$。

stk[++top] = 1; 
for(int i = 2; i <= n; i++){
    int u, v;
    while(top > 1){
        u = stk[top], v = stk[top - 1];
        if(1ll * (b[u] - b[v]) * (i - u) < 1ll * (b[i] - b[u]) * (u - v)) break;
        top--;
    }
    stk[++top] = i;
}
int p = 1, ans = 0x3f3f3f3f;
for(int i = 1; i <= n; i++){
    int u = stk[p], v = stk[p + 1];
    while(p < top && b[v] - 2 * i * v < b[u] - 2 * i * u) 
        p++, u = v, v = stk[p + 1];
    u = stk[p], ans = min(ans, a[i] + b[u] - 2 * i * u);
}

常幂展开在贡献法中的应用

看一道好题：

给出简单无向图 $G=(V,E)$，设 $S=(V_S,E_S)$ 为 $G$ 的某个导出子图，求 $\sum\limits_{S\subseteq G}|E_S|^k$。
$|V|,|E|\le 10^5, 1\le k\le 3$

显然，当 $k=1$ 时，我们可以运用贡献法考虑每条边对答案的贡献，因此得到答案即是 $|E|2^{|V|-2}$。

但是当 $k\ge 2$ 时，因为乘幂运算的缘故，直接使用贡献法是不可以的。根据常幂展开公式，我们可以这样给柿子变形：
$$ \begin{aligned}\sum\limits_{S\subseteq G}|E_S|^k= \sum\limits_{i=0}^k \begin{Bmatrix}k\newline i\end{Bmatrix}i!\sum\limits_{S\subseteq G}\dbinom{|E_S|}{i} \end{aligned} $$ 注意到这是求和，因此贡献法又适用了，那我们可以考虑求后面的 $\sum\limits_{S\subseteq G}\dbinom{|E_S|}{i}$。
考虑这个柿子的意义，我们可以等价于在原图中任意钦点 $i$ 条边出来，统计所有情况下包含 $i$ 条边的导出子图的数量。即我们考虑钦点一个组合数选出来的东西，然后考虑它的贡献，即它被选到的次数。

我们分类讨论。设边数为 $m$，点数为 $n$，对于 $k=2(i=(0),1,2)$ 的情况，可以这样分类：

$i=1$，即选一条边，显然是 $m2^{n-2}$；
$i=2$，即选两条边。注意到两条边可以共用一个端点，或者有四个独立的端点。我们只需要对这两种情况分别统计“方案数x被导出子图包含的次数”即可。

$k=3$ 的情况也可以类似的进行分类，于是就可以完成了。复杂度的瓶颈在于 $k=3$ 时的三元环计数，因此复杂度 $O(m^{1.5})$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int P = 1e9 + 7;
const int CN = 1e5 + 50;
const int i2 = 5e8 + 4;
const int i3 = 333333336;
int read(){
    int s = 0, ne = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int C(int x) {return 1ll * (1ll * x * (x - 1) % P) * i2 % P;}
int n, m, k, pw[CN], du[CN]; 
namespace sub1 {void work(){printf("%lld", 1ll * m * pw[n - 2] % P);}}
namespace sub2 {
void work(){
    int ans = 1ll * m * pw[n - 2] % P, s1 = 0, s2 = 0; // i = 1
    for(int i = 1; i <= m; i++){
        int x = read(), y = read(); du[x]++, du[y]++;
    }
    for(int i = 1; i <= n; i++) s1 = add(s1, C(du[i]));
    s2 = add(C(m), P - s1);
    if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P; else s1 = 0;
    if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P; else s2 = 0;
    s1 = add(s1, s2);
    ans = add(ans, add(s1, s1));
    printf("%d", ans);
}}
namespace sub3 {
int X[CN], Y[CN], col[CN]; vector<int> G[CN];
bool le(int i, int j) {return du[i] ^ du[j] ? du[i] < du[j] : i < j;}
void work(){
    int ans = 0, cnt1 = 1ll * m * pw[n - 2] % P, cnt2 = 0, cnt3 = 0;
    for(int i = 1; i <= m; i++){
        int x = read(), y = read(); 
        du[x]++, du[y]++, X[i] = x, Y[i] = y;
    }
    int s1 = 0, s2 = 0, s3 = 0, s4 = 0;  
    /* cnt2 */
    for(int i = 1; i <= n; i++) s1 = add(s1, C(du[i]));
    s2 = add(C(m), P - s1);
    if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P;
    else s1 = 0;
    if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P;
    else s2 = 0;
    cnt2 = add(s1, s2);
    /* cnt3 */
    s1 = s2 = s3 = s4 = 0;
    for(int i = 1; i <= m; i++){
        int u = X[i], v = Y[i];
        if(le(u, v)) G[v].pb(u); // v > u : v -> u
        else G[u].pb(v);
    }
    for(int i = 1; i <= n; i++){
        for(int l = G[i].size(), j = 0; j < l; j++) col[G[i][j]] = i;
        for(int l = G[i].size(), t = 0; t < l; t++){
            int j = G[i][t];
            for(int ll = G[j].size(), tt = 0; tt < ll; tt++)
                if(col[G[j][tt]] == i) s1++;
        }
    }
    for(int i = 1; i <= m; i++) s2 = add(s2, 1ll * (du[X[i]] - 1) * (du[Y[i]] - 1) % P);
    s2 = add(s2, P - (3ll * s1 % P));
    for(int i = 1; i <= n; i++) s3 = add(s3, 1ll * C(du[i]) * (m - du[i]) % P);
    s3 = add(s3, P - add(3ll * s1 % P, 2ll * s2 % P));
    for(int i = 1; i <= n; i++){
        int cur = 1ll * C(du[i]) * (du[i] - 2) % P; cur = 1ll * cur * i3 % P;
        s2 = add(s2, cur);
    }
    s4 = 1ll * C(m) * (m - 2) % P, s4 = 1ll * s4 * i3 % P;
    s4 = add(s4, P - add(add(s1, s2), s3));
    if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P; else s1 = 0;
    if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P; else s2 = 0;
    if(n >= 5) s3 = 1ll * s3 * pw[n - 5] % P; else s3 = 0;
    if(n >= 6) s4 = 1ll * s4 * pw[n - 6] % P; else s4 = 0;
    cnt3 = add(add(s1, s2), add(s3, s4));
    /* answer */
    cnt2 = 6ll * cnt2 % P, cnt3 = 6ll * cnt3 % P;
    ans = add(cnt1, add(cnt2, cnt3)), printf("%d", ans);
}}
int main()
{
    n = read(), m = read(), k = read();
    pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = add(pw[i - 1], pw[i - 1]);
    if(k == 1) sub1 :: work();
    if(k == 2) sub2 :: work();
    if(k == 3) sub3 :: work();
    return 0;
}

Lorem Ipsum

一个新的技巧：

众所周知，将 $m$ 划分为 $n$ 个非负整数有 $\dbinom{m+n-1}{n-1}$ 种方案。对于任意方案 $P$，我们定义 $val_k(P)$ 表示该划分中第 $k$ 大的数（降序排序后的第 $k$ 个）。设 $S$ 为总方案集，现在给定 $m,n,k$，请求出 $\sum\limits_{P\in S}val_k(P)$。
$n,m\le 5000$

设 $f[k,l]$ 表示一个划分中至少有 $k$ 个数字 $\ge l$ 的划分的数量。首先有等式：
$$ \sum\limits_{P\in S} val_k(P) =\sum\limits_{l=1}^mf[k,l] $$ 这个可以这样理解：我们考虑对于任意一个方案中第 $k$ 大的数，设它是 $p$，那么对于 $\forall l\le p$ 的 $f[k,l]$，$p$ 都会在 $f[k,l]$ 中被累加一次，一共累加 $p$ 次，因此这样是正确的。

那么现在的问题是求出“至少有 $k$ 个数字 $\ge l$ 的划分数”，这是一个“至少”限制，因此不可以直接选出来。可以这样理解：直接拿组合数选出来的是“钦定某 $k$ 个数字 $\ge l$ 的划分数”，而我们要求的是“有任意至少 $k$ 个数字 $\ge l$ 的划分数”。

形式化的说，设 $g[k,l]$ 为“恰好 $k$ 个数字 $\ge l$ 的划分数”，$h[k,l]$ 为“钦定 $k$ 个数字 $\ge l$ 的划分数”，$f[k,l]$ 为“至少有 $k$ 个数字 $\ge l$ 的划分数”，那么有：
$$ \begin{align} h[k,l]&=\dbinom{n}{k}\dbinom{m-kl+n-1}{n-1}\newline &=\sum\limits_{j=k}^n\dbinom{j}{k}g[j,l] \newline \Leftrightarrow g[k,l]&=\sum\limits_{j=k}^n(-1)^{j-k}\dbinom{j}{k}\dbinom{n}{k}\dbinom{m-kl+n-1}{n-1} \end{align}$$ 即是二项式反演，注意到这里实现了“钦定”到“恰好”的转化。“恰好”到“至少”的转化也可以类似的表示：
$$ \begin{align} f[k,l]&=\sum\limits_{j=k}^n g[j,l]\newline \Leftrightarrow g[k,l]&=f[k,l]-f[k+1,l] \end{align} $$ 总结来说，二项式反演联系了“钦定”与“恰好”限制，前/后缀和和差分联系了“至少”和“恰好”限制。

用 set 维护线段覆盖

看这样一个问题：

给出 $n$ 条线段 $[l_1,r_1],…[l_n,r_n]$，$q$ 次询问编号在 $[a,b]$ 内的线段覆盖的总长度是多少。
$n,q\le 10^5, l_i, r_i \le 10^9$

首先离线询问，把每个询问挂在询问区间的右端点上。考虑枚举询问的右端点 $b$，并用数据结构来维护每个 $i(i\le b)$ 的答案。

考虑怎样能快速地维护。如果对数轴上的每一个点维护一下它最后一次被覆盖是在什么时候（没覆盖就是 0），那么可以发现数轴会被划分成若干值相同的连续段。注意到同一时刻连续段的数量只有 $O(n)$ 种，那么我们考虑用 set 去维护这个东西。

具体来说，我们可以维护一个二元组 $(r,t)$，其中 $r$ 是当前连续段的分界点（右端点），$t$ 是当前连续段最晚被覆盖的时间。我们考虑新加入一个段 $(r_i,i)$，那么首先所有与其有交的连续段都会受到影响。具体来说，会有一些连续段被完全覆盖，即等价于删除，还有至多两个连续段会被分裂成两部分，其中一部分被保留，另一部分被替代。

我们考虑如果删除了一个连续段 $(r’,t’)$，它的长度是 $l$，那么左端点在 $[t’+1,i]$ 内区间的答案都会被加上 $l$，因为当前连续段的影响从 $t’$ 扩大到了 $i$。那么我们需要一个数据结构，支持区间加和单点求值，那么套一个 BIT 就可以解决了。时间复杂度是 $O(n\log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define iter set<PAIR> :: iterator
const int CN = 1e5 + 50;
int read(){
    int s = 0, ne = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}
class PAIR {
  public: int x, y;
    bool operator < (const PAIR &o) const {return x ^ o.x ? x < o.x : y < o.y;}
};
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
set<PAIR> S; vector<PAIR> Q[CN];
int n, m, L[CN], R[CN], ans[CN];
class BIT {
  public: int d[CN];
    void add(int p, int x) {while(p <= n) d[p] += x, p += p & (-p);}
    void md(int l, int r, int x) {add(l, x), add(r + 1, -x);}
    int qu(int p) {int r = 0; while(p) r += d[p], p -= p & (-p); return r;}
} D;
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++) L[i] = read(), R[i] = read();
    for(int i = 1; i <= m; i++){
        int l = read(), r = read();
        Q[r].pb(mp(l, i));
    }
    S.insert(mp(1e9, 0));
    for(int i = 1; i <= n; i++){
        int l = L[i], r = R[i], fst = -1, prv = l - 1;
        iter it = S.lower_bound(mp(l, 0));
        while(1){
            if(it == S.end()) break;
            int cur = (*it).x, p = (*it).y, len;
            if(fst < 0) fst = p;
            len = min(cur, r) - prv, D.md(p + 1, i, len);
            if(cur <= r){
                prv = cur;
                iter pit = it; it++, S.erase(pit);
            }
            else break;
        }
        if(l > 1) S.insert(mp(l - 1, fst));
        S.insert(mp(r, i));
        for(int l = Q[i].size(), j = 0; j < l; j++)
            ans[Q[i][j].y] = D.qu(Q[i][j].x);
    }
    for(int i = 1; i <= m; i++) printf("%d", ans[i]), puts("");
    return 0;
}