牛仔周刊》第 39 期（A,B,C,D,E,F,G） - F 小红不愿意做模拟训练

思路：

区间修改，区间查询，还是比较明显能想到线段树的。

当我们区间推平时，比如推平了 $a$ 串的区间 $[l,r]$，把它变成 $1$，那么这一段区间 $1$ 的对数就变成了 $b$ 串这段区间中 $1$ 的个数，同理推平另一个串。所以我们为了维护区间 $1$ 的对数，还需要分别维护住 $a,b$ 串区间内 $1$ 的个数。

另外因为这个题只进行了一个简单的推平操作，所以我们也不需要写懒节点并将节点信息向下传递，我们只要在线段树节点上打个标记，表示是否推平了，之后修改或者查询的时候查到标记就直接返回就行了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;

int n,q;
string str[2];

struct segment_tree{
	#define ls p<<1
	#define rs p<<1|1
	
	struct Node{
		int l,r;
		int a,b;//区间内 a串1的个数，b串1的个数
		int sam;//ab串同为1的位置的个数
		bool fa,fb;//是否填平
		Node(int l=0,int r=0,int a=0,int b=0,int sam=0,bool fa=false,bool fb=false):l(l),r(r),a(a),b(b),sam(sam),fa(fa),fb(fb){}; 
	}tr[maxn<<4];
	
	void push_up(int p){
		auto& [l,r,a,b,sam,fa,fb]=tr[p];
		
		a=(fa)?r-l+1:tr[ls].a+tr[rs].a;
		b=(fb)?r-l+1:tr[ls].b+tr[rs].b;
		
		if(fa)sam=tr[p].b;
		else if(fb)sam=tr[p].a;
		else sam=tr[ls].sam+tr[rs].sam;
	}
	void build(int p,int l,int r){
		tr[p].l=l;
		tr[p].r=r;
		if(l==r){
			tr[p].a=(str[0][l-1]=='1');
			tr[p].b=(str[1][l-1]=='1');
			tr[p].sam=(tr[p].a && tr[p].b);
			return;
		}
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(p);
	}
	void print(int p,int l,int r){
		printf("%d [%d,%d]:%d %d %d\n",p,l,r,tr[p].a,tr[p].b,tr[p].sam);
		if(l==r){
			return;
		}
		int mid=l+r>>1;
		print(ls,l,mid);
		print(rs,mid+1,r);
	}
	void print(){print(1,1,n);}
	
	void modify(int p,int l,int r,int L,int R,bool st){
		if(L<=l && r<=R){
			if(st){//填平a串 
				tr[p].a=r-l+1;
				tr[p].fa=true;
				tr[p].sam=tr[p].b;
			}
			else {//填平b串 
				tr[p].b=r-l+1;
				tr[p].fb=true;
				tr[p].sam=tr[p].a;
			}
			return;
		}
		int mid=l+r>>1;
		if(mid>=L)modify(ls,l,mid,L,R,st);
		if(mid<R)modify(rs,mid+1,r,L,R,st);
		push_up(p);
	}
	int q(){return tr[1].sam;}
	
	#undef ls
	#undef rs
}tr;

int main(){
//	cin.tie(0)->sync_with_stdio(false);
	
	cin>>n>>str[0]>>str[1];
	tr.build(1,1,n);
	for(cin>>q;q;q--){
		char ch;
		int l,r;
		cin>>ch>>l>>r;
		tr.modify(1,1,n,l,r,(ch=='A'));
		cout<<tr.q()<<endl;
//		tr.print();
//		cout<<endl;
	}
	return 0;
}