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

• 2018-02-18
• 0
• 0

Problem:

题目描述

你有一个长度为 $n$ 的数列 a_n​，这个数列由 $0,1$ 组成，进行 $m$ 个操作：

1 l r ：把数列区间 $[l,r]$ 内的所有数取反。即 $0$ 变成 $1$ ，$1$ 变成 $0$ 。

2 l r ：询问数列在区间 $[l,r]$ 内共有多少个本质不同的子序列。

输入输出格式

输入格式：

第一行包含两个整数 $n,m$ ，意义如上所述。

接下来一行包含 $n$ 个数，表示数列 a_n​。

接下来 $m$ 行，每行包含三个数，表示一个操作，操作格式如上所述。

输出格式：

对于每个询问，输出答案模 10⁹+7 的结果。

输入输出样例

4 4
1 0 1 0
2 1 4
2 2 4
1 2 3
2 1 4

11
6
8

说明

对于 $10\%$ 的数据，1≤n,m≤10²。

对于 $30\%$ 的数据，1≤n,m≤10³。

对于 $100\%$ 的数据，1≤n,m≤10⁵。

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(3³mlogn) [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;
}