AtCoder abc256全题解（区间合并模板、矩阵快速幂优化dp、线段树……）

• • • A
    • B
    • C-枚举
    • D-区间合并模板
    • E-图论建模，函数图的性质
    • • 题意
      • 思路
      • 代码
    • F-树状数组
    • • 题意
      • 思路
      • 代码
    • G-矩阵快速幂优化dp
    • H-线段树
    • • 思路
      • 实现

本文CSDN

本文juejin

作者：hans774882968以及hans774882968

水，略。

模拟即可。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 5 + 5;

int n, a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (n);
    int ans = 0;
    rep (_, 1, n) {
        int x;
        read (x);
        a[0]++;
        dwn (i, 3, 0) {
            if (i + x < 4) a[i + x] += a[i];
            else ans += a[i];
            a[i] = 0;
        }
    }
    printf ("%dn", ans);
    return 0;
}

题意：有一个九宫格，每格填一个正整数，输入3 <= h[0~2] <= 30, 3 <= w[0~2] <= 30分别表示期望的每行和每列的数字的和。求方案数。

只需要枚举4个格子就能确定所有的数了，计算量30^4完全可行。我选择的是(0,0), (0,1), (1,0), (1,1)这4个格子。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, w[5], h[5];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    n = 3;
    re_ (i, 0, n) read (w[i]);
    re_ (i, 0, n) read (h[i]);
    int ans = 0;
    re_ (i0, 1, min (w[0], h[0]) - 1) {
        re_ (i1, 1, min (w[1], h[0]) - 1) {
            re_ (i3, 1, min (w[0], h[1]) - 1) {
                re_ (i4, 1, min (w[1], h[1]) - 1) {
                    int i2 = h[0] - i0 - i1, i5 = h[1] - i3 - i4, i6 = w[0] - i0 - i3, i7 = w[1] - i1 - i4;
                    if (i2 > 0 && i5 > 0 && i6 > 0 && i7 > 0) {
                        int i81 = h[2] - i6 - i7, i82 = w[2] - i2 - i5;
                        if (i81 == i82 && i81 > 0) ++ans;
                    }
                }
            }
        }
    }
    printf ("%dn", ans);
    return 0;
}

区间合并模板，参考：https://blog.nowcoder.net/n/834a656e47df44e58e830fdd87d3e253。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n;
pii a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    read (n);
    rep (i, 1, n) read (a[i].first, a[i].second);
    sort (a + 1, a + n + 1);
    vector ans;
    for (int i = 1; i <= n; ++i) {
        int l = a[i].first, r = a[i].second;
        while (i <= n && a[i + 1].first <= r) r = max (r, a[++i].second);
        ans.push_back ({l, r});
    }
    for (pii v : ans) printf ("%d %dn", v.first, v.second);
    return 0;
}

n <= 2e5个人排队拿糖果。输入长为n的两个数组x, c，表示如果i号人排在x[i]号人后面，则i号人会受到c[i]的伤害。请你求一个排列，使所有人受到的总伤害最小。保证i ≠ x[i]。

尝试往逆序对、二分、贪心和自定义排序等方面想，一无所获。只好看答案，没想到是图论题！

这个图有n条有向边，i -> x[i]，官方题解指出这种图叫做functional graph，顾名思义，以i为自变量，x[i]为因变量，确实符合函数定义。函数图有如下特殊性质：它的每个无向图意义下的连通分量恰好有一个环。官方题解用数学归纳法，用了不少篇幅来证明。其实感性上更好理解：每个点都必须有一个出度，而DAG拓扑序最大的点出度为0，故必定有环。而环套环要求有些点出度至少为2。

这样每个连通分量就分为非环的部分和环上的部分。对于非环的部分x1 -> x2 -> ...，直接定顺序为x1 -> x2 -> ...伤害为0，最优。环上的部分至少有一个人会受伤害。那么我们只让伤害值最小的人受伤即可，贡献min(c[y1],c[y2],...)。

1. uf[]标记无向图意义下的连通分量是否被访问过。简单的并查集。
2. 为了得到环上的所有点：vis[]是中间变量，u从i开始，跳到第一次vis[u] = true的时候，u是环上的一点，接着跳就能得到环上的所有点了。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, c[N], a[N], fa[N];
bool vis[N], uf[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int find (int x) {
    return x == fa[x] ? x : fa[x] = find (fa[x]);
}

int main() {
    read (n);
    re_ (i, 0, n) read (c[i]), c[i]--;
    re_ (i, 0, n) read (a[i]);
    re_ (i, 0, n) fa[i] = i;
    re_ (i, 0, n) {
        int f1 = find (i), f2 = find (c[i]);
        fa[f1] = f2;
    }
    LL ans = 0;
    re_ (i, 0, n) {
        int fi = find (i);
        if (uf[fi]) continue;
        uf[fi] = true;
        vis[i] = true;
        int u = c[i];
        while (!vis[u]) {
            vis[u] = true;
            u = c[u];
        }
        int mn = a[u];
        for (int v = c[u]; v != u; v = c[v])
            mn = min (mn, a[v]);
        ans += mn;
    }
    printf ("%lldn", ans);
    return 0;
}

给你长为n <= 2e5的数组。有两种操作：

1. 单点修改。
2. 求3阶前缀和D[x]（见原题，1-indexed），模998244353。

套路题。首先考虑把它写成只与a[1], a[2], ..., a[x]有关的形式。对于二阶前缀和，用贡献思想很容易发现是C[x] = x*a[1]+(x-1)*a[2]+...+1*a[x]，所以D[x] = (x+2-1)*(x+1-1)/2*a[1]+(x+2-2)*(x+1-2)/2*a[1]+...+(x+2-x)*(x+1-x)/2*a[x]。

对于(x+2-i)*(x+1-i)/2*a[i]，我们希望x的函数与和i有关的函数分离，则x的函数是系数，和i有关的函数是需要维护的数组，这样题目就做完了。分离出(x+2)*(x+1)/2 * a[i] - (2*x+3)/2 * (i*a[i]) + 1/2 * (i*i*a[i])。因此只需要维护a[i], i*a[i], i*i*a[i]的前缀和。

拓展：k阶前缀和同理可做。但k较大的时候是否能写代码来求多项式系数呢？我暂时做不到。

• 注意一切皆可模法。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define lowbit(x) ((x) & (-(x)))

const int N = 2e5 + 5;
const int mod = 998244353;
const int I2 = 499122177;

int n, q, a[N];
LL c0[N], c1[N], c2[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

void mdy (LL C[], int x, LL v) {
    for (; x <= n; x += lowbit (x) ) C[x] = (C[x] + v) % mod;
}

LL qry (LL C[], int x) {
    LL ret = 0;
    for (; x; x -= lowbit (x) ) ret = (ret + C[x]) % mod;
    return ret;
}

int main() {
    read (n, q);
    rep (i, 1, n) read (a[i]), a[i] %= mod;
    rep (i, 1, n) {
        mdy (c0, i, a[i]);
        mdy (c1, i, 1LL * i * a[i] % mod);
        mdy (c2, i, 1LL * i * i % mod * a[i] % mod);
    }
    while (q--) {
        int op;
        read (op);
        if (op == 1) {
            int x;
            LL v;
            read (x, v);
            v %= mod;
            mdy (c0, x, (v - a[x] + mod) % mod);
            mdy (c1, x, x * (v - a[x] + mod) % mod);
            mdy (c2, x, 1LL * x * x % mod * (v - a[x] + mod) % mod);
            a[x] = v;
        } else {
            LL x;
            read (x);
            LL k0 = (x + 2) * (x + 1) % mod * I2 % mod, k1 = (2 * x + 3) * I2 % mod;
            LL ans = (k0 * qry (c0, x) % mod - k1 * qry (c1, x) % mod + I2 * qry (c2, x) % mod + mod) % mod;
            printf ("%lldn", ans);
        }
    }
    return 0;
}

太难了，只能想到2^D的做法（枚举顶点颜色的状态位），直接学习题解了……

定义dp[i][S = 0~3]为填了前i条边，第一个顶点和当前的边的顶点的颜色分别为状态位的高位和低位的方案数，1表示白色（1表示黑色同理可做）。显然第n条边的顶点和第一个顶点颜色要相同，所以答案dp[n][0] + dp[n][3]。

但我们发现没法转移，因为不知道之前的白色有几种，没法保证白色点数相同。那白色点数相同的保证就用外部限制来实现，所以我们先枚举所需颜色种类数k = 0~D+1。转移：dp[i][S] = sum(C(D - 1, k - bc[S1]) * dp[i-1][S0])，这里S和S0的高位要相同，而S1 = (S % 2) << 1 | (S0 % 2)表示上一条边的顶点和当前边的顶点颜色组成的状态位，bc[]表示白色点的个数。边界：dp[1][S] = C(D - 1, k - bc[S])。

转移只与i-1有关，可矩阵快速幂优化。

总结：想法要大胆，看到n较大也不一定就放弃思考dp做法了，因为还可以用矩阵快速幂来保证复杂度。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 1e4 + 5;
const int mod = 998244353;

LL pw, fac[N], ifac[N];
int D, n = 4;

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

struct Mat {
    LL m[5][5];
    Mat() {
        memset (m, 0, sizeof m);
    }
};
Mat mul (Mat a, Mat b) {
    Mat ret;
    re_ (i, 0, n) {
        re_ (j, 0, n) {
            LL s = 0;
            re_ (k, 0, n) s = (s + a.m[i][k] * b.m[k][j] % mod) % mod;
            ret.m[i][j] = s;
        }
    }
    return ret;
}
Mat q_pow (Mat a, LL b) {
    Mat ret;
    re_ (i, 0, n) ret.m[i][i] = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = mul (ret, a);
        a = mul (a, a);
    }
    return ret;
}

LL q_pow (LL a, LL b) {
    LL ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret;
}

void init_C (int n) {
    fac[0] = 1;
    rep (i, 1, n) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = q_pow (fac[n], mod - 2);
    dwn (i, n - 1, 0) ifac[i] = (i + 1) * ifac[i + 1] % mod;
}

LL C (int x, int y) {
    if (y < 0 || x < y) return 0;
    return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

int main() {
    init_C (N - 5);
    read (pw, D);
    LL ans = 0;
    rep (k, 0, D + 1) {
        Mat m0, bas;
        re_ (S, 0, n) {
            re_ (S0, 0, n) {
                if (S / 2 != S0 / 2) continue;
                int u = (S % 2) << 1 | (S0 % 2);
                m0.m[S][S0] = C (D - 1, k - __builtin_popcount (u) );
            }
        }
        re_ (S, 0, n) bas.m[S][0] = C (D - 1, k - __builtin_popcount (S) );
        Mat m1 = mul (q_pow (m0, pw - 1), bas);
        ans = (ans + m1.m[0][0] + m1.m[3][0]) % mod;
    }
    printf ("%lldn", ans);
    return 0;
}

即ex题。官方题解的两种做法都太难了，但是操作1的区间向下整除会导致数字快速减小，而操作2的区间覆盖会导致整个数组的丰富程度下降，所以我们会想尝试加一个tag，表示区间的数字是否完全相同，在区间数字完全相同时停止往下遍历。

加这个tag的思路的主要来源是这道线段树模板题：花神游历各国，hdu上有一道题，区间求欧拉函数+求区间和，也是一样的思路。

加这个tag的思路很容易理解，也能AC，但我不清楚它在这题的复杂度对不对。

1. 结构体需要3个属性：v,ctg,s。v = -1表示该区间的值不是完全相同，v >= 0表示值完全相同；ctg表示区间覆盖的懒标记；s表示区间和。
2. 我选择了先build，再对数组进行n次单点覆盖，这就要求把叶节点的值设为0，而非叶节点的ctg设为-1。也可以直接读入数组再build。
3. s不是可选的而是必须的，把s去掉则查区间和的时候会走得更深，导致TLE。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int N = 5e5 + 5;

int n, q;

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

struct Node {
    int v, ctg;
    LL s;
} nd[N << 2];

void update (int x, int v, int l, int r) {
    nd[x].ctg = nd[x].v = v;
    nd[x].s = 1LL * v * (r - l + 1);
}

void pushup (int x) {
    nd[x].v = nd[ls (x)].v == nd[rs (x)].v ? nd[ls (x)].v : -1;
    nd[x].s = nd[ls (x)].s + nd[rs (x)].s;
}

void pushdown (int x, int l, int r) {
    if (!~nd[x].ctg) return;
    int v = nd[x].ctg, mid = (l + r) >> 1;
    nd[ls (x)].ctg = nd[rs (x)].ctg = v;
    nd[ls (x)].v = nd[rs (x)].v = v;
    nd[ls (x)].s = (mid - l + 1LL) * v;
    nd[rs (x)].s = 1LL * (r - mid) * v;
    nd[x].ctg = -1;
}

void build (int x, int l, int r) {
    nd[x].ctg = -1;
    if (l == r) {
        update (x, 0, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    build (ls (x), l, mid);
    build (rs (x), mid + 1, r);
    pushup (x);
}

void idiv (int ql, int qr, int v, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr && ~nd[x].v) {
        update (x, nd[x].v / v, l, r);
        return;
    }
    pushdown (x, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) idiv (ql, qr, v, ls (x), l, mid);
    if (qr > mid) idiv (ql, qr, v, rs (x), mid + 1, r);
    pushup (x);
}

void cover (int ql, int qr, int v, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr && ~nd[x].v) {
        update (x, v, l, r);
        return;
    }
    pushdown (x, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) cover (ql, qr, v, ls (x), l, mid);
    if (qr > mid) cover (ql, qr, v, rs (x), mid + 1, r);
    pushup (x);
}

LL qry (int ql, int qr, int x = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) return nd[x].s;
    pushdown (x, l, r);
    int mid = (l + r) >> 1;
    LL ans = 0;
    if (ql <= mid) ans += qry (ql, qr, ls (x), l, mid);
    if (qr > mid) ans += qry (ql, qr, rs (x), mid + 1, r);
    pushup (x);
    return ans;
}

int main() {
    read (n, q);
    build (1, 1, n);
    rep (i, 1, n) {
        int v;
        read (v);
        cover (i, i, v);
    }
    while (q--) {
        int op, l, r, v;
        read (op, l, r);
        if (op == 1) {
            read (v);
            idiv (l, r, v);
        } else if (op == 2) {
            read (v);
            cover (l, r, v);
        } else {
            printf ("%lldn", qry (l, r) );
        }
    }
    return 0;
}