C++14(g++5.4) 解法, 执行用时: 368ms, 内存消耗: 24028K, 提交时间: 2018-10-05 13:11:30

#include<bits/stdc++.h>
using namespace std;


const int MAX_N = 3e5 + 5;
struct nd {
	int m[2][2];
	nd(int x = 0) {
		m[0][1] = m[1][0] = 1;
		m[0][0] = x;
		m[1][1] = !x;
	}
}dat[MAX_N * 4];

int cnt = 0;
char s[MAX_N];
int n, q, a, b;

nd merge(nd a, nd b) {
	nd c;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			c.m[i][j] = min(a.m[i][0] + b.m[0][j], a.m[i][1] + b.m[1][j]);
		}
	}
	return c;
}

void build(int l, int r, int k) {
	if (r - l == 1) {
	    dat[k] = nd(s[cnt++]^'0');
		return;
	}
	build(l, (l + r) >> 1, 2 * k + 1);
	build((l + r) >> 1, r, 2 * k + 2);
	dat[k] = merge(dat[2 * k + 1], dat[2 * k + 2]);
}

nd query(int a, int b, int l, int r, int k) {
	if (a <= l && r <= b) return dat[k];
	if (b <= l || a >= r) return nd(0);
	return merge(query(a, b, l, (l + r) >> 1, 2 * k + 1),
		query(a, b, (l + r) >> 1, r, 2 * k + 2));
}

void change(int l, int r, int k) {
	if (a < l || a >= r) return;
	if (r - l == 1) {
		dat[k] = nd(b);
		return;
	}
	change(l, (l + r) >> 1, 2 * k + 1);
	change((l + r) >> 1, r, 2 * k + 2);
	dat[k] = merge(dat[2 * k + 1], dat[2 * k + 2]);
}

int main() {
	cin >> n; scanf("%s", &s);
	build(0, n, 0);
	cin >> q;
	int t;
	for (int i = 0; i < q; i++) {
		scanf("%d%d%d", &t, &a, &b);
		if (t == 1) {
			printf("%d\n",query(a - 1, b, 0, n, 0).m[0][0]);
		}
		else {
			a--;
			change(0, n, 0);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 339ms, 内存消耗: 21472K, 提交时间: 2018-10-29 16:50:54

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=3e5+10;
int n,q,A[N];char s[N];
struct Mat {int a[4];Mat(){a[0]=a[1]=a[2]=a[3]=0;}}t[N<<2];
Mat operator + (Mat A,Mat B)
{
	Mat C;
	C.a[0]=min(A.a[0]+B.a[0],A.a[1]+B.a[2]);
	C.a[1]=min(A.a[0]+B.a[1],A.a[1]+B.a[3]);
	C.a[2]=min(A.a[2]+B.a[0],A.a[3]+B.a[2]);
	C.a[3]=min(A.a[2]+B.a[1],A.a[3]+B.a[3]);
	return C;
}
void Get(Mat &A) {A.a[0]=A.a[1]=A.a[2]=A.a[3]=1;}
void build(int now,int l,int r,int p,int v)
{
	if(l==r)
	{
		if(p) A[l]=v;Get(t[now]);
		t[now].a[A[l]?3:0]=0;
		return;
	}
	int mid=(l+r)>>1;
	if(!p||p<=mid) build(now<<1,l,mid,p,v);
	if(!p||p>mid) build(now<<1|1,mid+1,r,p,v);
	t[now]=t[now<<1]+t[now<<1|1];
}
Mat Query(int now,int l,int r,int gl,int gr)
{
	if(l>=gl&&r<=gr) return t[now];
	int mid=(l+r)>>1;
	if(gr<=mid) return Query(now<<1,l,mid,gl,gr);
	if(gl>mid) return Query(now<<1|1,mid+1,r,gl,gr);
	return Query(now<<1,l,mid,gl,gr)+Query(now<<1|1,mid+1,r,gl,gr);
}
int main()
{
	scanf("%d%s%d",&n,s+1,&q);
	for(int i=1;i<=n;i++) A[i]=s[i]=='1';
	build(1,1,n,0,0);
	while(q--)
	{
		int op,x,y;scanf("%d%d%d",&op,&x,&y);
		if(op==1) printf("%d\n",Query(1,1,n,x,y).a[0]);
		else if(A[x]!=y) build(1,1,n,x,y);
	}
	return 0;
}