发表于 | 分类于 | 0 | 阅读次数 741

更好的阅读体验

题目描述

题目传送门

思路

先忽视区间查询，比较好想到的是动态规划，设 fi,0/1/2/3/4f_{i,0/1/2/3/4} 分别表示 [1,i][1,i] 分别满足含有 ∅/2/20/201/2017\varnothing/2/20/201/2017 子序列且没有 20162016 的方案数。

接下来大力转移：

  • fi,0f_{i,0} 的转移

fi,0f_{i,0} 需要删的时候，就是出现了 22，那么很容易得到转移为：

fi,0=fi−1,0+[s=2]f_{i,0} = f_{i-1,0}+ [s=2]

  • fi,1f_{i,1} 的转移

fi,1f_{i,1} 需要删的时候，就是前面出现了 22，并且这里出现了 00，或者这里第一次出现 22，那么很容易得到转移为：

fi,1=min⁡{fi−1,1+[si=0]fi−1,0if⁡si=2+∞f_{i,1} = \min\begin{cases} f_{i-1,1} + [s_i = 0]\\ f_{i-1,0}\quad \operatorname{if} s_i = 2\\ +\infty \end{cases}

  • fi,2f_{i,2} 的转移

fi,2f_{i,2} 需要删的时候，就是前面出现了 2020，并且这里出现了 11，或者前面出现了 22，并且这里出现了 00，那么很容易得到转移为：

fi,2=min⁡{fi−1,2+[si=1]fi−1,1if⁡si=0+∞f_{i,2} = \min\begin{cases} f_{i-1,2} + [s_i = 1]\\ f_{i-1,1}\quad \operatorname{if} s_i = 0\\ +\infty \end{cases}

  • fi,3f_{i,3} 的转移

fi,3f_{i,3} 需要删的时候，就是前面出现了 201201，并且这里出现了 66 或者 77，或者前面出现了 2020，并且这里出现了 11，那么很容易得到转移为：

fi,3=min⁡{fi−1,3+[si∈{6,7}]fi−1,2if⁡si=1+∞f_{i,3} = \min\begin{cases} f_{i-1,3} + [s_i \in \{6,7\}]\\ f_{i-1,2}\quad \operatorname{if} s_i = 1\\ +\infty \end{cases}

  • fi,4f_{i,4} 的转移

fi,4f_{i,4} 需要删的时候，就是前面出现了 20172017，并且这里出现了 66，或者前面出现了 201201，并且这里出现了 77，那么很容易得到转移为：

fi,4=min⁡{fi−1,4+[si=6]fi−1,3if⁡si=7+∞f_{i,4} = \min\begin{cases} f_{i-1,4} + [s_i = 6]\\ f_{i-1,3}\quad \operatorname{if} s_i = 7\\ +\infty \end{cases}

然后转移就做完了。

观察到数据范围很大，考虑矩阵快速幂优化，很容易想到首先要新定义矩阵乘法：

Ci,j=min⁡1≤k≤n{Ai,k+Bk,j}\mathbf{C}_{i,j} = \min_{1 \le k \le n}\{ \mathbf{A}_{i,k} + \mathbf{B}_{k,j}\}

然后，我们可以把动态规划写成矩阵：

定义运算 f([expression])f([expression]):

g([expression])={0if⁡ expression is true∞  Otherwise⁡g([expression])=\begin{cases} 0\quad\quad \operatorname{if}\ \text{expression is true}\\ \infty \quad \ \ \operatorname{Otherwise} \end{cases}

[fi,0fi,1fi,2fi,3fi,4]=[fi−1,0fi−1,1fi−1,2fi−1,3fi−1,4]×[[si=2]g([si=2])+∞+∞+∞+∞[si=0]g([si=1])+∞∞+∞+∞[si=1]g([si=1])∞+∞+∞+∞[si∈{6,7}]g([si=7])+∞+∞+∞+∞[si=6]]\begin{bmatrix} f_{i,0} \\ f_{i,1} \\ f_{i,2}\\ f_{i,3} \\ f_{i,4} \end{bmatrix} = \begin{bmatrix} f_{i - 1,0}\\ f_{i - 1,1}\\ f_{i - 1,2}\\ f_{i - 1,3}\\ f_{i - 1,4} \end{bmatrix} \mathbf{\times} \begin{aligned} \begin{bmatrix} [s_i=2]& \quad g([s_i=2])& \quad +\infty& \quad +\infty& \quad +\infty\\ +\infty& \quad [s_i=0]& \quad g([s_i=1])&\quad +\infty& \quad \infty\\ +\infty& \quad +\infty& \quad [s_i=1]& \quad g([s_i = 1])& \quad \infty\\ +\infty& \quad +\infty& \quad +\infty& \quad [s_i \in \{6,7\}]& \quad g([s_i=7])\\ +\infty& \quad +\infty& \quad +\infty& \quad +\infty& \quad [s_i=6]\\ \end{bmatrix} \end{aligned}

然后，我们由于要查询区间的答案，那么用 SMT 维护区间矩阵乘法，然后设区间 [l,r][l,r] 转移矩阵的积为 C\mathbf{C}，那么答案为：

[0∞∞∞∞]×C\begin{bmatrix} 0\\ \infty\\ \infty\\ \infty\\ \infty\\ \end{bmatrix} \times \mathbf{C}

然后就做完了，时间复杂度 Θ(qlog⁡n)\Theta(q\log n)，常数极大。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN_Matrix = 5, MAXN = 2e5 + 10;

struct Matrix {
    int M[MAXN_Matrix][MAXN_Matrix];
    Matrix() {
        memset(M, 0x3f, sizeof M);
    }
    Matrix friend operator*(Matrix x, Matrix y) {
        Matrix res;
        for (int i = 0; i < MAXN_Matrix; i++) {
            for (int j = 0; j < MAXN_Matrix; j++) {
                for (int k = 0; k < MAXN_Matrix; k++) {
                    res.M[i][j] = min(res.M[i][j], x.M[i][k] + y.M[k][j]);
                }
            }
        }
        return res;
    }

    Matrix friend operator^(Matrix x, Matrix y) {
        Matrix res;
        for (int i = 0; i < MAXN_Matrix; i++) {
            for (int j = 0; j < MAXN_Matrix; j++) {
                res.M[0][i] = min(res.M[0][i], x.M[0][j] + y.M[j][i]);
            }
        }
        return res;
    }
} SMT[MAXN << 2], Ans, Prime, G[MAXN];

void Build(int p, int l, int r) {
    if (l == r) {
        SMT[p] = G[l];
        return;
    }
    int mid = l + r >> 1;
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    SMT[p] = SMT[p << 1] * SMT[p << 1 | 1];
}

void Query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        Ans = Ans ^ SMT[p];
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) Query(p << 1, l, mid, ql, qr);
    if (mid < qr) Query(p << 1 | 1, mid + 1, r, ql, qr);
}

int N, P;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> P;
    Prime.M[0][0] = 0;
    for (int i = 1; i <= N; i++) {
        static char S;
        cin >> S;
        for (int j = 0; j < MAXN_Matrix; j++) G[i].M[j][j] = 0;
        if (S == '2') {
            G[i].M[0][0] = 1;
            G[i].M[0][1] = 0;
        }
        if (S == '0') {
            G[i].M[1][1] = 1;
            G[i].M[1][2] = 0;
        }
        if (S == '1') {
            G[i].M[2][2] = 1;
            G[i].M[2][3] = 0;
        }
        if (S == '7') {
            G[i].M[3][3] = 1;
            G[i].M[3][4] = 0;
        }
        if (S == '6') {
            G[i].M[3][3] = 1;
            G[i].M[4][4] = 1;
        }
    }
    Build(1, 1, N);
    for (int i = 1; i <= P; i++) {
        static int l, r;
        cin >> l >> r;
        Ans = Prime;
        Query(1, 1, N, l, r);
        cout << (Ans.M[0][4] <= N ? Ans.M[0][4] : -1) << endl;
    }
    return 0;
}