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

• 2018-02-18
• 0
• 0

## Problem:

### 题目描述

：把数列区间 内的所有数取反。即 变成 变成

：询问数列在区间 内共有多少个本质不同的子序列。

### 输入输出样例

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

11
6
8

## Solution:

• 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;
}


#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai