[洛谷春令营 D1T1] 子序列【线段树+矩阵加速】

  • 2018-02-18
  • 0
  • 0

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] + 1f[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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai