[洛谷春令营 D1T1] 子序列【线段树+矩阵加速】
Problem:
题目描述
你有一个长度为 的数列 ,这个数列由 组成,进行 个操作:
:把数列区间 内的所有数取反。即 变成 , 变成 。
:询问数列在区间 内共有多少个本质不同的子序列。
输入输出格式
输入格式:
第一行包含两个整数 ,意义如上所述。
接下来一行包含 个数,表示数列 。
接下来 行,每行包含三个数,表示一个操作,操作格式如上所述。
输出格式:
对于每个询问,输出答案模 的结果。
输入输出样例
输入样例#1:
4 4 1 0 1 0 2 1 4 2 2 4 1 2 3 2 1 4
输出样例#1:
11 6 8
说明
对于 的数据,。
对于 的数据,。
对于 的数据,。
Solution:
这是一道很巧妙的数据结构题。
此处 “本质不同” 只要子序列在原序列中出现位置不完全相同即可。
考虑静态的 DP,我们发现若设 f[i][j] 为前 i 个数中以 j 结尾的本质不同子序列个数,则有
- 若 a[i] == 0,则 f[i][0] = f[i - 1][0] + f[i - 1][1] + 1,f[i][1] = f[i - 1][1]。
- 若 a[i] == 1,则 f[i][0] = f[i - 1][0],f[i][1] = f[i - 1][0] + f[i - 1][1] + 1。
由于这是一个递推式,我们可以将其写成矩阵乘法形式:
而将某一点的值取反,该点的矩阵只需要先交换前两行,再交换前两列。
进一步可以发现,若区间内所有值都取反,区间的矩阵积也可以这样处理。
所以我们可以用线段树来维护区间的矩阵积。
Code: O(33mlogn) [31562K, 1292MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 100002; const ll MOD = 1000000007; inline void getint(int &num){ char ch; while(!isdigit(ch = getchar())); num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; } int n, m, a[MAXN], opt, l, r; struct Matrix{ ll v[4][4]; inline Matrix operator * (const Matrix mat2) const { Matrix mat3; mat3.v[1][1] = (v[1][1] * mat2.v[1][1] + v[1][2] * mat2.v[2][1] + v[1][3] * mat2.v[3][1]) % MOD; mat3.v[1][2] = (v[1][1] * mat2.v[1][2] + v[1][2] * mat2.v[2][2] + v[1][3] * mat2.v[3][2]) % MOD; mat3.v[1][3] = (v[1][1] * mat2.v[1][3] + v[1][2] * mat2.v[2][3] + v[1][3] * mat2.v[3][3]) % MOD; mat3.v[2][1] = (v[2][1] * mat2.v[1][1] + v[2][2] * mat2.v[2][1] + v[2][3] * mat2.v[3][1]) % MOD; mat3.v[2][2] = (v[2][1] * mat2.v[1][2] + v[2][2] * mat2.v[2][2] + v[2][3] * mat2.v[3][2]) % MOD; mat3.v[2][3] = (v[2][1] * mat2.v[1][3] + v[2][2] * mat2.v[2][3] + v[2][3] * mat2.v[3][3]) % MOD; mat3.v[3][1] = (v[3][1] * mat2.v[1][1] + v[3][2] * mat2.v[2][1] + v[3][3] * mat2.v[3][1]) % MOD; mat3.v[3][2] = (v[3][1] * mat2.v[1][2] + v[3][2] * mat2.v[2][2] + v[3][3] * mat2.v[3][2]) % MOD; mat3.v[3][3] = (v[3][1] * mat2.v[1][3] + v[3][2] * mat2.v[2][3] + v[3][3] * mat2.v[3][3]) % MOD; return mat3; } }; struct Node{ Matrix mat; bool invflag; Node *lc, *rc; inline void update() {mat = lc->mat * rc->mat;} inline void inv(){ swap(mat.v[1][1], mat.v[2][1]), swap(mat.v[1][2], mat.v[2][2]), swap(mat.v[1][3], mat.v[2][3]); swap(mat.v[1][1], mat.v[1][2]), swap(mat.v[2][1], mat.v[2][2]), swap(mat.v[3][1], mat.v[3][2]); } inline void pushdown(){ if(invflag){ lc->invflag ^= 1, rc->invflag ^= 1; lc->inv(), rc->inv(); invflag = 0; } } }; Node pool[MAXN << 1]; inline Node* newNode(){ static int topp = 0; return &pool[topp++]; } inline Node* build(int *a, int l, int r){ Node *cur = newNode(); if(l == r){ if(a[l] == 0) cur->mat.v[1][1] = cur->mat.v[2][1] = cur->mat.v[3][1] = cur->mat.v[2][2] = cur->mat.v[3][3] = 1; else cur->mat.v[1][1] = cur->mat.v[1][2] = cur->mat.v[2][2] = cur->mat.v[3][2] = cur->mat.v[3][3] = 1; } else{ int smid = l + r >> 1; cur->lc = build(a, l, smid), cur->rc = build(a, smid + 1, r); cur->update(); } return cur; } inline void inverse(Node *cur, int l, int r, int invl, int invr){ if(l == invl && r == invr) {cur->inv(), cur->invflag ^= 1; return;} cur->pushdown(); int smid = l + r >> 1; if(invr <= smid) inverse(cur->lc, l, smid, invl, invr); else if(invl > smid) inverse(cur->rc, smid + 1, r, invl, invr); else inverse(cur->lc, l, smid, invl, smid), inverse(cur->rc, smid + 1, r, smid + 1, invr); cur->update(); } inline Matrix query(Node *cur, int l, int r, int ql, int qr){ if(l == ql && r == qr) return cur->mat; cur->pushdown(); int smid = l + r >> 1; if(qr <= smid) return query(cur->lc, l, smid, ql, qr); else if(ql > smid) return query(cur->rc, smid + 1, r, ql, qr); else return query(cur->lc, l, smid, ql, smid) * query(cur->rc, smid + 1, r, smid + 1, qr); } int main(){ getint(n), getint(m); for(register int i = 1; i <= n; i++) getint(a[i]); Node *root = build(a, 1, n); for(register int i = 1; i <= m; i++){ getint(opt), getint(l), getint(r); if(opt == 1) inverse(root, 1, n, l, r); else{ Matrix res = query(root, 1, n, l, r); printf("%lld\n", (res.v[3][1] + res.v[3][2]) % MOD); } } return 0; }
发表评论