nowcoder wannafly 25 E：01串

E：01 串

分析：
　　线段树维护转移矩阵。每个节点是一个矩阵，区间内的矩阵乘起来就是答案矩阵。矩阵乘法满足结合律，所以线段树维护。
代码：
 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cctype>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 #define Root 1, n, 1
12 #define lson l, mid, rt << 1
13 #define rson mid + 1, r, rt << 1 | 1
14 using namespace std;
15 typedef long long LL;
16 
17 inline int read() {
18     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
19     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
20 }
21 
22 const int N = 300005;
23 char s[N];
24 struct Node{
25     int a[2][2];
26     void Calc(int v) {
27         if (v) a[0][0] = 1, a[1][0] = 1, a[0][1] = 2, a[1][1] = 0;
28         else a[0][0] = 0, a[1][0] = 2, a[0][1] = 1, a[1][1] = 1;
29     }
30 }T[N << 2];
31 Node operator + (const Node &A,const Node &B) {
32     Node C; memset(C.a, 0x3f, sizeof(C.a));
33     for (int k = 0; k < 2; ++k)
34         for (int i = 0; i < 2; ++i)     
35             for (int j = 0; j < 2; ++j) 
36                 C.a[i][j] = min(C.a[i][j], A.a[i][k] + B.a[k][j]);
37     return C;
38 }
39 void build(int l,int r,int rt) {
40     if (l == r) { T[rt].Calc(s[l] - '0'); return ; }
41     int mid = (l + r) >> 1;
42     build(lson); build(rson);
43     T[rt] = T[rt << 1] + T[rt << 1 | 1];
44 }
45 void update(int l,int r,int rt,int p,int v) {
46     if (l == r) { T[rt].Calc(v); return ; }
47     int mid = (l + r) >> 1;
48     if (p <= mid) update(lson, p, v);
49     else update(rson, p, v);
50     T[rt] = T[rt << 1] + T[rt << 1 | 1];
51 }
52 Node query(int l,int r,int rt,int L,int R) {
53     if (L <= l && r <= R) return T[rt];
54     int mid = (l + r) >> 1;
55     if (R <= mid) return query(lson, L, R);
56     else if (L > mid) return query(rson, L, R);
57     else return query(lson, L, R) + query(rson, L, R);
58 }
59 int main() {
60     int n = read();
61     scanf("%s", s + 1);
62     build(Root);
63     Node ans;
64     for (int Q = read(); Q--; ) {
65         int opt = read(), x = read(), y = read();
66         if (opt == 1) {
67             ans = query(Root, x, y);
68             printf("%d
",min(ans.a[0][0], ans.a[1][0] + 1));
69         }
70         else update(Root, x, y);
71     }
72     return 0;
73 }