# New Year and Old Subsequence CodeForces - 750E（线段树 + 矩阵）

## New Year and Old Subsequence (CodeForces - 750E)

#### 题意：

$$n,q<=200000$$。

#### 题解：

$a=\left[ \begin{matrix} 1 & 0 & \inf & \inf & \inf \\inf & 0 & \inf & \inf & \inf \\inf & \inf & 0 & \inf & \inf \\inf & \inf & \inf & 0 & \inf \\inf & \inf & \inf & \inf & 0 \end{matrix} \right]$

$a=\left[ \begin{matrix} 0 & \inf & \inf & \inf & \inf \\inf & 0 & \inf & \inf & \inf \\inf & \inf & 0 & \inf & \inf \\inf & \inf & \inf & 1 & \inf \\inf & \inf & \inf & \inf & 1 \end{matrix} \right]$

#### 代码

#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef long long LL;

char s[maxn];

struct Matrix {
int m[5][5];
Matrix() { memset(m, 0x3f, sizeof(m)); }
Matrix operator * (const Matrix &rhs) {
Matrix res;
for (int k = 0; k <= 4; k++)
for (int i = 0; i <= 4; i++)
for (int j = 0; j <= 4; j++)
res.m[i][j] = min(res.m[i][j], m[i][k] + rhs.m[k][j]);
return res;
}
};

struct SegTree {
struct Node {
int l, r;
Matrix M;
}t[maxn * 4];

void build(int id, int l, int r) {
t[id].l = l, t[id].r = r;
if (l == r) {
for (int i = 0; i <= 4; i++) t[id].M.m[i][i] = 0;
if (s[l] == '2') { t[id].M.m[0][0] = 1; t[id].M.m[0][1] = 0; }
if (s[l] == '0') { t[id].M.m[1][1] = 1; t[id].M.m[1][2] = 0; }
if (s[l] == '1') { t[id].M.m[2][2] = 1; t[id].M.m[2][3] = 0; }
if (s[l] == '7') { t[id].M.m[3][3] = 1; t[id].M.m[3][4] = 0; }
if (s[l] == '6') { t[id].M.m[3][3] = 1; t[id].M.m[4][4] = 1; }
return;
}
int mid = (l+r) / 2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
t[id].M = t[id*2].M * t[id*2+1].M;
}

Matrix query(int id, int l, int r) {
if (l <= t[id].l && r >= t[id].r) return t[id].M;
int mid = (t[id].l + t[id].r) / 2;
if (r <= mid) return query(id*2, l, r);
else if (l > mid) return query(id*2+1, l, r);
return query(id*2, l, mid) * query(id*2+1, mid+1, r);
}
}T;

int l, r, n, q;
int main() {
//fopi;
scanf("%d%d", &n, &q);
scanf("%s", s+1);
T.build(1, 1, n);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &l, &r);
int res = T.query(1, l, r).m[0][4];
printf("%d\n", res >= inf ? -1 : res);
}
}

## ZOJ 3772 Calculate the Function 线段树+矩阵

Calculate the FunctionTime Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit Status Appoint description:  System Crawler  (2014-04-09) Description You are given a list of numbers A1A2 .. AN and M queries. For the i-th query

## Codeforces 833B 线段树优化 dp

Codeforces  833B  The Bakery 题意: n 个数要分成 k 块,每块的价值是其不同数的个数,问价值和最大是多少. tags: dp[i][j]表示前 j 个数分成 i 块的最大权值和,转移: dp[i][j] = max( dp[i-1][k] + val[k+1][j] ) , k是 1~j . 但这个过程其实并不好转移,要利用累加的特点,用线段树进行优化 (感觉我不看题解是想不到的,2333) 大概就是,对于第 i 层,我们假定已经知道了第 i-1 层,也就是求出了

## 线段树 + 矩阵 --- ZOJ 3772 Calculate the Function

Calculate the Function Problem's Link:   http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3772 Mean: 略 analyse: 简单的线段树维护矩阵. 矩阵乘法的结合律(a * b * c == a * (b * c)),注意矩阵乘法不满足分配率(a *b != b * a). 令 M[x] = [1 A[x]]              [1     0 ] ,那么有 [ F

## 河南省多校联盟二-F 线段树+矩阵

---恢复内容开始--- 1284: SP教数学 时间限制: 2 秒  内存限制: 128 MB提交: 24  解决: 4 题目描述 输入 输出 对于每组数据的2操作,输出一行对1e9 + 7取模的答案 样例输入 7 4 2 2 1 1 3 3 2 2 1 5 2 6 7 1 3 4 3 2 6 6 样例输出 6 3 2 提示 1 <=  n ,m <=10^5 一道很有趣的ST的题目,有趣在维护节点时用到了矩阵运算,减少了计算量. 首先对于矩阵运算法则,百度百科: 基本性质 乘法结合律: (