Codeforces 750 E New Year and Old Subsequence

E. New Year and Old Subsequence

思路：线段树维护矩阵乘法。

代码：
#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define y1 y11

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb emplace_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define pdd pair<double, double>

#define mem(a, b) memset(a, b, sizeof(a))

#define debug(x) cerr << #x << " = " << x << "\n";

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

//head

const int INF = 0x3f3f3f3f;

const int N = 2e5 + 10;

struct Matrix {

    int a[5][5];

    inline void init() {

        memset(a, INF, sizeof a);

    }

    inline Matrix operator * (const Matrix & rhs) const {

        Matrix res;

        res.init();

        for (int k = 0; k < 5; ++k) {

            for (int i = 0; i < 5; ++i) {

                for (int j = 0; j < 5; ++j) {

                    res.a[i][j] = min(res.a[i][j], a[i][k]+rhs.a[k][j]);

                }

            }

        }

        return res;

    }

}tree[N<<2];

char s[N];

int n, q, l, r;

inline int push_up(int rt) {

    tree[rt] = tree[rt<<1]*tree[rt<<1|1];

}

/* |2|0|1|7| */

void build(int rt, int l, int r) {

    if(l == r) {

        tree[rt].init();

        for (int i = 0; i < 5; ++i) tree[rt].a[i][i] = 0;

        if(s[l] == '2') tree[rt].a[0][1] = 0, tree[rt].a[0][0] = 1;

        else if(s[l] == '0') tree[rt].a[1][2] = 0, tree[rt].a[1][1] = 1;

        else if(s[l] == '1') tree[rt].a[2][3] = 0, tree[rt].a[2][2] = 1;

        else if(s[l] == '7') tree[rt].a[3][4] = 0, tree[rt].a[3][3] = 1;

        else if(s[l] == '6') tree[rt].a[3][3] = 1, tree[rt].a[4][4] = 1;

        return ;

    }

    int m = l+r >> 1;

    build(ls);

    build(rs);

    push_up(rt);

}

Matrix query(int L, int R, int rt, int l, int r) {

    if(L <= l && r <= R) return tree[rt];

    int m = l+r >> 1;

    Matrix res;

    res.init();

    for (int i = 0; i < 5; ++i) res.a[i][i] = 0;

    if(L <= m) res = res * query(L, R, ls);

    if(R > m) res = res* query(L, R, rs);

    return res;

}

int main() {

    scanf("%d %d", &n, &q);

    scanf("%s", s+1);

    build(1, 1, n);

    while(q--) {

        scanf("%d %d", &l, &r);

        Matrix res = query(l, r, 1, 1, n);

        if(res.a[0][4] == INF) printf("-1\n");

        else printf("%d\n", res.a[0][4]);

    }

    return 0;

}
巴特西

Codeforces 750 E New Year and Old Subsequence

最新文章

热门文章
