斐波那契数列的区间操作

题目：华尔街的雪

题目大意：

斐波那契序列 f_n 满足 f_0=f_1=1,f_{n+2}=f_n+f_{n+1}，n 为自然数。现在有 n 个可重集合排成一列，编号分别为 1-n，每个集合初始包含一个数 f_1。请支持如下四种操作：
1. 在第l~r号集合中各加入一个斐波那契数 f_k
2. 第l~r号集合中所有的斐波那契数 f_x 变为 f_{x+k}
3. 第l~r号集合中所有的斐波那契数变为 f_k
4. 查询l~r号集合中所有斐波那契数的和除以 6324 所得余数。

请注意，l-r号表示编号在区间 [l,r] 的那些集合。

解题思路：

用矩阵表示斐波那契数，用线段树维护矩阵。每个线段树节点维护两个信息：

• 当前节点的矩阵 t[rt]
• 当前节点的数的数量 num[rt]

维护四个懒标记：

• Mat lz1[rt]：表示此区间乘以了 lz1[rt]
• Mat lz2[rt]：表示此区间的所有矩阵都被替换为了 lz2[rt]
• Mat lz3[rt]：表示此区间加上了 lz3[rt]
• int lz4[rt]：表示此区间的每个集合都被放置了 lz4[rt] 个矩阵

考虑每种操作：

第一种操作，等同于区间加矩阵，我们对 t[rt] 和 num[rt] 进行相应变化，同时打上 lz3 和 lz4 标记；
第二种操作，等同于区间乘矩阵，我们对 t[rt] 和 lz1进行相应变化，同时打上 lz3 标记；
第三种操作，前面打的标记全部失效清零；我们对 t[rt] 进行相应变化，同时打上 lz2 标记；
查询时，只要获得对应区间的矩阵即可。

考虑标记的下传：

首先要处理好子节点每个集合的元素个数问题，即下传 lz4 标记；
由于添加 lz2 时会清空 lz1 和 lz3，因此 lz1 和 lz3 会在 lz2 被添加，所以我们先处理 lz2。将 lz2 下传，同时也把子节点原有的 lz1 和 lz3 清空；
再下传 lz1 和 lz3，和普通线段树维护加法乘法类似。

#include <bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int P = 6324;
const int N = 2e5 + 50;
int n, m;

struct Mat {
    int a[2][2];
    Mat() {
        memset(a, 0, sizeof(a));
    }
    void init() {
        a[0][0] = a[1][1] = 1;
        a[1][0] = a[0][1] = 0;
    }
    void clear() {
        memset(a, 0, sizeof(a));
    }
    bool empty() {
        if (a[0][0] || a[0][1] || a[1][0] || a[1][1]) {
            return false;
        }
        return true;
    }
    Mat operator * (const Mat &x) const {
        Mat ret;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    ret.a[i][j] += a[i][k] * x.a[k][j] % P;
                }
                ret.a[i][j] %= P;
            }
        }
        return ret;
    }
    Mat operator * (const int &x) const {
        Mat ret = *this;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                (ret.a[i][j] *= x) %= P;
            }
        }
        return ret;
    }
    Mat operator + (const Mat &x) const {
        Mat ret;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                ret.a[i][j] = (a[i][j] + x.a[i][j]) % P;
            }
        }
        return ret;
    }
    Mat operator ^ (const int &x) const {
        Mat ret, a = *this;
        int b = x;
        ret.init();
        for (; b; b >>= 1, a = a * a) {
            if (b & 1) ret = ret * a;
        }
        return ret;
    }
};

Mat base;
Mat t[N << 2], lz1[N << 2], lz2[N << 2], lz3[N << 2];
int num[N << 2], lz4[N << 2];
void pushup(int rt) {
    t[rt] = t[ls] + t[rs];
    num[rt] = num[ls] + num[rs];
}
void addtag2(int rt, Mat &x) {
    t[rt] = x * num[rt];
    lz1[rt].init(); lz2[rt] = x; lz3[rt].clear();
}
void pushdown(int rt, int l, int r) {
    num[ls] += lz4[rt] * (mid - l + 1);
    num[rs] += lz4[rt] * (r - mid);
    lz4[ls] += lz4[rt]; lz4[rs] += lz4[rt];
    lz4[rt] = 0;
    if (!lz2[rt].empty()) {
        addtag2(ls, lz2[rt]); addtag2(rs, lz2[rt]);
        lz2[rt].clear();
    }
    t[ls] = t[ls] * lz1[rt] + lz3[rt] * (mid - l + 1);
    lz1[ls] = lz1[ls] * lz1[rt];
    lz3[ls] = lz3[ls] * lz1[rt] + lz3[rt];
    t[rs] = t[rs] * lz1[rt] + lz3[rt] * (r - mid);
    lz1[rs] = lz1[rs] * lz1[rt];
    lz3[rs] = lz3[rs] * lz1[rt] + lz3[rt];

    lz1[rt].init();
    lz3[rt].clear();
}
void build(int rt, int l, int r) {
    lz1[rt].init();
    lz2[rt].clear();
    lz3[rt].clear();
    if (l == r) {
        t[rt] = base; num[rt] = 1; return;
    }
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(rt);
}

void modify(int rt, int l, int r, int L, int R, Mat &x, int op) {
    if (r < L || l > R) return;
    if (l >= L && r <= R) {
        if (op == 1) {
            t[rt] = t[rt] + x * (r - l + 1);
            num[rt] += r - l + 1;
            lz3[rt] = lz3[rt] + x;
            lz4[rt]++;
        }
        else if (op == 2) {
            lz1[rt] = lz1[rt] * x;
            lz3[rt] = lz3[rt] * x;
            t[rt] = t[rt] * x;
        }
        else if (op == 3) addtag2(rt, x);
        return;
    }
    pushdown(rt, l, r);
    modify(ls, l, mid, L, R, x, op);
    modify(rs, mid + 1, r, L, R, x, op);
    pushup(rt);
}

Mat query(int rt, int l, int r, int L, int R) {
    Mat ret;
    if (r < L || l > R) return ret;
    if (l >= L && r <= R) return t[rt];
    pushdown(rt, l, r);
    return query(ls, l, mid, L, R) + query(rs, mid + 1, r, L, R);
}
int query(int L, int R) {
    return query(1, 1, n, L, R).a[1][1];
}

int main(int argc, const char * argv[]) {
    base.a[0][1] = base.a[1][0] = base.a[1][1] = 1;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for (int i = 1, o, l, r, x; i <= m; i++) {
        scanf("%d", &o);
        if (o < 4) {
            scanf("%d%d%d", &l, &r, &x);
            Mat tmp = base ^ x;
            modify(1, 1, n, l, r, tmp, o);
        }
        if (o == 4) {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(l, r));
        }
    }
    return 0;
}

线段树维护自动机状态转移

题目链接：CF750E New Year and Old Subsequence

题目大意：

定义一个数字串满足性质 nice 当且仅当：该串包含子串 2017，且不包含子串 2016。

定义一个数字串的函数 ugliness 为：该串至少删去几个字符，可以使得剩余串满足性质 nice；如果该串没有满足性质 nice 的子串，则该串的 ugliness 是 −1。

给定一个长度为 n 的字符串 t，和 q 次询问，每次询问用 (l,r) 表示。对于每次询问，回答 ugliness(t[l,r])。

解题思路：

考虑如下 5 种状态：
状态0：空状态 or 初始状态
状态1：包含序列“2”
状态2：包含序列“20”
状态3：包含序列“201”
状态4：包含序列“2017”

我们将从 i 状态转移到 j 状态的过程看作一条花费为 c 的边，则我们可以得到“2”，“0”，“1”，“7”，“6” 这 5 个字符所对应的自动机，并且把这样 5\times 5 的状态转移边放到一个矩阵中，就可以简易地表示自动机。

switch (s[l]) {
    case '2' : t[rt].v[0][0] = 1; t[rt].v[0][1] = 0; break;
    case '0' : t[rt].v[1][1] = 1; t[rt].v[1][2] = 0; break;
    case '1' : t[rt].v[2][2] = 1; t[rt].v[2][3] = 0; break;
    case '7' : t[rt].v[3][3] = 1; t[rt].v[3][4] = 0; break;
    case '6' : t[rt].v[4][4] = 1; t[rt].v[3][3] = 1; break;
}

这 5 个矩阵未被声明的元素都被定义为 inf（主对角线为 0），表明当前自动机在接收这个字符时（这 5 种字符），由 i 状态转移到 j 状态的最小花费为多少。拿 s[i] = 2 来举例，若当前自动机需要接受字符“2”，则从 0 状态（空状态）转移到 1 状态（包含序列“2”），所需最小花费为 0 ；而从 0 状态转移到自身的最小花费为 1，因为必须要删除当前所接受的字符；同时，其他除了主对角线上的转移都是不合法的，因此保留 inf 边，且主对角线上的所有转移（自身转移到自身）都是不需要有任何花费的，因为发生不了转移。后面 4 种矩阵同理。特别的，在当前自动机接受字符“6”时，从 3 状态（包含序列“201”）到自身，必须删除这个“6”才行，因此花费为 1；从 4状态（包含序列“2017”）到自身，也必须删除掉这个“6”才行，因此花费也为 1。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 2e5 + 50;
int n, q;
char s[N];

struct Matrix {
    int v[5][5];
    void init() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                v[i][j] = (i == j ? 0 : INF);
            }
        }
    }
    Matrix operator * (const Matrix &a) {
        Matrix ret;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ret.v[i][j] = INF;
                for (int k = 0; k < 5; k++) {
                    ret.v[i][j] = min(ret.v[i][j], v[i][k] + a.v[k][j]);
                }
            }
        }
        return ret;
    }
};

#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
Matrix t[N << 2];
void build(int rt, int l, int r) {
    if (l == r) {
        t[rt].init();
        switch (s[l]) {
            case '2' : t[rt].v[0][0] = 1; t[rt].v[0][1] = 0; break;
            case '0' : t[rt].v[1][1] = 1; t[rt].v[1][2] = 0; break;
            case '1' : t[rt].v[2][2] = 1; t[rt].v[2][3] = 0; break;
            case '7' : t[rt].v[3][3] = 1; t[rt].v[3][4] = 0; break;
            case '6' : t[rt].v[4][4] = 1; t[rt].v[3][3] = 1; break;
        }
        return;
    }
    build(ls, l, mid); build(rs, mid + 1, r);
    t[rt] = t[ls] * t[rs];
}
Matrix query(int rt, int l, int r, int L, int R) {
    if (l >= L && r <= R) return t[rt];
    if (mid < L) return query(rs, mid + 1, r, L, R);
    else if (mid >= R) return query(ls, l, mid, L, R);
    return query(ls, l, mid, L, R) * query(rs, mid + 1, r, L, R);
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    build(1, 1, n);
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        int ans = query(1, 1, n, l, r).v[0][4];
        printf("%d\n", ans < N ? ans : -1);
    }
    return 0;
}