P7453 大魔法师 Sol

从 OI – Wiki 上跑过来的。

首先看到区间操作，考虑线段树。

看到轮换式这样朴素线段树维护不了的东西，考虑矩阵乘法。

因为矩阵乘法具有结合律，所以线段树区间合并支持矩阵合并。

状态很好设，显然三个数组以及一个常数，\([A,B,C,x]\)。

下面令其每个元素的位置分别为 \(1,2,3,4\)。

这题大致解法就出来了，下面考虑细节。

\(1\) 至 \(3\) 操作如何解决

对于 \(1\) 操作，有 \([A,B,C,x]\leftarrow[A+B,B,C,x]\)。

考虑一个 \(4\times4\) 的矩阵 \(M\) 和原状态 \([A,B,C,x]\) 的关系。

对于第一列来说，第一列从上往下第 \(i\) 个元素 \(a_{i,1}\) 表示往目标状态的第一个位置添加 \(a_{i,1}\times A\)。

同理可推出 \(B,C,x\) 的规律。

那么很显然，当前矩阵应该为

\(\begin{bmatrix}1\space\space0\space\space0\space\space0\\1\space\space1\space\space0\space\space0\\0\space\space0\space\space1\space\space0\\0\space\space0\space\space0\space\space1\end{bmatrix}\)

目标位置 \(1\) 为 \(1\times A+1\times B+0\times C+0\times x=A+B\)。

即终止状态为 \([A+B,B,C,x]\)。

同理可以推出 \(2\) 操作和 \(3\) 操作的矩阵。

\(\begin{bmatrix}1\space\space0\space\space0\space\space0\\0\space\space1\space\space0\space\space0\\0\space\space1\space\space1\space\space0\\0\space\space0\space\space0\space\space1\end{bmatrix}\)

\(\begin{bmatrix}1\space\space0\space\space1\space\space0\\0\space\space1\space\space0\space\space0\\0\space\space0\space\space1\space\space0\\0\space\space0\space\space0\space\space1\end{bmatrix}\)

\(4\) 至 \(7\) 操作如何解决

同理，\(4\) 操作为 \([A,B,C,x]\leftarrow[A+v,B,C,x]\)。

考虑利用常数项 \(x\)。

特殊地，在线段树的叶子节点，\(x=1\)。

那么考虑 \([A,B,C,1]\leftarrow[A+v,B,C,1]\)。

考虑在目标位置 \(1\) 加入系数为 \(v\) 的常数项 \(1\)。具体地，矩阵长这样。

\(\begin{bmatrix}1\space\space0\space\space0\space\space0\\0\space\space1\space\space0\space\space0\\0\space\space0\space\space1\space\space0\\v\space\space0\space\space0\space\space1\end{bmatrix}\)

那么目标位置 \(1\) 为 \(1\times A+0\times B+0\times C+v\times 1=A+v\)，搞定。

对于 \(5\) 操作，变为乘法，考虑把目标位置 \(2\) 变为系数为 \(v\) 的 \(B\)，矩阵长这样。

\(\begin{bmatrix}1\space\space0\space\space0\space\space0\\0\space\space v\space\space0\space\space0\\0\space\space0\space\space1\space\space0\\0\space\space0\space\space0\space\space1\end{bmatrix}\)

目标位置 \(2\) 为 \(0\times A+v\times B+0\times C+0\times 1=v\times B\)。

同理有 \(6\) 操作，直接把目标位置 \(2\) 变为系数为 \(v\) 的常数项 \(1\)。

\(\begin{bmatrix}1\space\space0\space\space0\space\space0\\0\space\space 1\space\space0\space\space0\\0\space\space0\space\space0\space\space 0\\0\space\space0\space\space v\space\space1\end{bmatrix}\)

目标位置 \(3\) 为 \(0\times A+0\times B+0\times C+v\times 1=v\)。

另外线段树 pushup 时区间的长度（即操作自带的系数）为两个子区间的长度和而非 \(1\)。

考虑在 pushup 的时候更新常数项 \(x=r-l+1\)，即区间长度，作为区间全体操作的系数。

由于所有要维护的信息都是可以直接合并的，所以对于 \(4\) 个元素 \([A,B,C,x]\) 直接在 pushup 时求和即可。

\(7\) 询问操作直接求区间和即可，返回一个结构体并且输出。

pushdown 怎么写

由于矩阵乘法具有结合律，所以在 pushdown 的时候可以直接把当前节点的懒标记乘进子结点的懒标记。

另外，初始化的时候记得将懒标记赋为单位矩阵，这样才满足初始时和一个序列做乘法不会错。

pushdown 完成后也要记得清空为单位矩阵。

另外，这题真的不卡常。

#include <bits/stdc++.h>
#define int long long
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
using namespace std;

const int sz = 4, N = 2.5e5 + 10;
const int Mod = 998244353; int n, Q; bool ok[N << 2];

namespace fast_io {
  int it, ed, ot, t; char stk[20], bf[N + 50], ob[N + 50];
  #define gc (it == ed && (ed = (it = 0) + fread(bf, 1, N, stdin), it == ed))? EOF : bf[it++]
  template <typename T> inline void read(T &x) {
    x = 0; char ch = gc; int f = 1;
    for (; !isdigit(ch); ch = gc) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = gc) x = x * 10 + (ch ^ 48); x *= f; return ;
  } template <typename T, typename ...Args>
  inline void read(T &x, Args &...args) { read(x), read(args...); }
  inline void fls() { fwrite(ob, 1, ot, stdout), ot = 0; }
  template <typename T> inline void write(T x, char opt) {
    while (x > 9) stk[++t] = 48 ^ (x % 10), x /= 10;
    for (ob[ot++] = 48 ^ x; t; ob[ot++] = stk[t--]);
    ob[ot++] = opt; if (ot > N) fls(); return ;
  }
} using fast_io::read; using fast_io::write;

struct Matrix {
  int v[sz][sz]; Matrix() { memset(v, 0, sizeof(v)); }
  inline void cl() { memset(v, 0, sizeof(v)); }
  inline void dl() { for (int i = 0; i < sz; ++i) v[i][i] = 1; }
  inline Matrix operator *(const Matrix &X) const {
    Matrix res; for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) for (int j = 0; j < sz; ++j)
        res.v[i][j] = (res.v[i][j] + v[i][k] * X.v[k][j] % Mod) % Mod;
    return res;
  }
} ml[7], tag[N << 2];

struct Node {
  int st[sz]; Node() { fill(st, st + sz, 0); }
  inline void init(int a, int b, int c) {
    st[0] = a, st[1] = b, st[2] = c, st[3] = 1;
  } inline Node operator *(const Matrix &X) {
    Node res; for (int j = 0; j < sz; ++j)
      for (int i = 0; i < sz; ++i)
        res.st[i] = (res.st[i] + st[j] * X.v[j][i] % Mod) % Mod;
    return res;
  } inline Node operator +(const Node &X) const {
    Node res; for (int i = 0; i < sz; ++i)
      res.st[i] = (st[i] + X.st[i]) % Mod;
    return res;
  }
} t[N << 2];

inline void init() {
  for (int i = 1; i <= 6; ++i) {
    for (int j = 0; j < sz; ++j) ml[i].v[j][j] = 1;
    if (i == 1) ml[i].v[1][0] = 1;
    else if (i == 2) ml[i].v[2][1] = 1;
    else if (i == 3) ml[i].v[0][2] = 1;
  }
  return ;
}

inline void pushdown(int rt, int l, int r) {
  if (!ok[rt]) return ; ok[ls] = ok[rs] = ok[rt];
  t[ls] = t[ls] * tag[rt], t[rs] = t[rs] * tag[rt];
  tag[ls] = tag[ls] * tag[rt], tag[rs] = tag[rs] * tag[rt];
  ok[rt] = false; tag[rt].cl(), tag[rt].dl(); return ;
}

inline void build(int rt, int l, int r) {
  tag[rt].dl();
  if (l == r) {
    int a, b, c; read(a, b, c);
    t[rt].init(a, b, c); return ;
  }
  int mid = (l + r) >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  t[rt] = t[ls] + t[rs]; return ;
}

inline void upd(int rt, int l, int r, int L, int R, int typ) {
  if (L <= l && r <= R) {
    t[rt] = t[rt] * ml[typ]; ok[rt] = true;
    tag[rt] = tag[rt] * ml[typ]; return ;
  }
  pushdown(rt, l, r); int mid = (l + r) >> 1;
  if (L <= mid) upd(ls, l, mid, L, R, typ); if (R > mid) upd(rs, mid + 1, r, L, R, typ);
  t[rt] = t[ls] + t[rs]; return ;
}

inline Node query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[rt];
  pushdown(rt, l, r); int mid = (l + r) >> 1;
  int tar = 0; Node lef, rig;
  if (L <= mid) ++tar, lef = query(ls, l, mid, L, R);
  if (R > mid) tar += 2, rig = query(rs, mid + 1, r, L, R);
  if (tar == 1) return lef; if (tar == 2) return rig;
  return lef + rig;
}

inline void solve() {
  int op, l, r, vl; read(op, l, r);
  if (op <= 3) return upd(1, 1, n, l, r, op), void();
  if (op <= 6) {
    read(vl); if (op == 4) ml[op].v[3][0] = vl;
    else if (op == 5) ml[op].v[1][1] = vl;
    else ml[op].v[2][2] = 0, ml[op].v[3][2] = vl;
    return upd(1, 1, n, l, r, op), void();
  }
  Node tmp = query(1, 1, n, l, r);
  for (int i = 0; i < sz - 1; ++i) write(tmp.st[i], ' ');
  fast_io::ob[fast_io::ot++] = '\n';
  if (fast_io::ot > N) fast_io::fls(); return ;
}

signed main() {
  init(); read(n); build(1, 1, n);
  read(Q); while (Q--) solve();
  fast_io::fls(); return 0;
}

原文地址：http://www.cnblogs.com/MistZero/p/P7453-Sol.html