本文共 2105 字，大约阅读时间需要 7 分钟。
分析：
。每个节点是一个矩阵，区间内的矩阵乘起来就是答案矩阵。矩阵乘法满足结合律，所以线段树维护。
代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define Root 1, n, 112 #define lson l, mid, rt << 113 #define rson mid + 1, r, rt << 1 | 114 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\n",min(ans.a[0][0], ans.a[1][0] + 1));69 }70 else update(Root, x, y);71 }72 return 0;73 }
转载于:https://www.cnblogs.com/mjtcn/p/10103375.html