求助qaq
  • 板块P2574 XOR的艺术
  • 楼主GaryH
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/7/17 16:22
  • 上次更新2023/11/6 22:57:34
查看原帖
求助qaq
100091
GaryH楼主2020/7/17 16:22

萌新刚学线段树,10pts求救

#include<bits/stdc++.h>
#define maxn 200000
using namespace std;
typedef long long ll;
string s;
ll n,m,a[maxn+5],OP,L,R;
struct Tree{
	ll l,r,sum;
	bool lazy;
	Tree *left,*right;
};
inline Tree* newtree(){return new Tree();}
inline void build(Tree** cur,ll l,ll r){
	(*cur)->sum=(*cur)->lazy=0;(*cur)->l=l,(*cur)->r=r;
	if(l+1<r){
		(*cur)->left=newtree(),(*cur)->right=newtree();
		build(&((*cur)->left),l,(l+r)/2);
		build(&((*cur)->right),(l+r)/2,r);
		(*cur)->sum=(*cur)->left->sum+(*cur)->right->sum;
	}else{
		(*cur)->left=(*cur)->right=NULL;(*cur)->sum=a[l];
	}
}
inline void update(Tree *cur){
	cur->left->sum=cur->left->r-cur->left->l-cur->left->sum;
	cur->right->sum=cur->right->r-cur->right->l-cur->right->sum;
	cur->left->lazy=cur->right->lazy=1;
}
inline ll query(Tree* cur,ll l,ll r){
	if(l<=cur->l&&r>=cur->r){
		return cur->sum;
	}
	if(cur->lazy)update(cur);
	ll ans=0;
	if(l<(cur->l+cur->r)/2)ans+=query(cur->left,l,r);
	if(r>(cur->l+cur->r)/2)ans+=query(cur->right,l,r);
	return ans;
}
inline void modify(Tree* cur,ll l,ll r){
	if(l<=cur->l&&r>=cur->r){
		cur->sum=cur->r-cur->l-cur->sum;
		cur->lazy=1;
		return;
	}
	if(cur->lazy)update(cur);
	if(l<(cur->l+cur->r)/2)modify(cur->left,l,r);
	if(r>(cur->l+cur->r)/2)modify(cur->right,l,r);
	cur->sum=cur->left->sum+cur->right->sum;
}
int main(){
	Tree* root=newtree();
	cin>>n>>m;
	cin>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='0')a[i+1]=0;
		else a[i+1]=1;
	}
	build(&root,1,n+1);
	for(int i=1;i<=m;i++){
		cin>>OP>>L>>R;
		if(OP==0)modify(root,L,R+1);
		if(OP==1)cout<<query(root,L,R+1)<<endl;
	}
	return 0;
}
2020/7/17 16:22
加载中...