线段树水题集合

用的都是《算法竞赛》的码风哦

洛谷P3870

极简 ，开和关用 1 0 表示 ，然后区间修改，区间求和，裸题

洛谷P2846

这两道题一模一样

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
#define ll long long
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
ll n,m,sum[N<<2];
bool tag[N<<2];
void addtag(ll p,ll pl,ll pr){
	sum[p]=pr-pl+1-sum[p];
	tag[p]=!tag[p];
}
void pushdown(ll p,ll pl,ll pr){
	if(tag[p]){
		ll mid=(pl+pr)>>1;
		addtag(ls(p),pl,mid);
		addtag(rs(p),mid+1,pr);
		tag[p]=!tag[p];
	}
}
void pushup(ll p){
	sum[p]=sum[ls(p)]+sum[rs(p)];
}
void update(ll p,ll L,ll R,ll pl,ll pr){
	if(L<=pl&&R>=pr){
		addtag(p,pl,pr);
		return;
	} 
	pushdown(p,pl,pr);
	ll mid=(pl+pr)>>1;
	if(L<=mid)update(ls(p),L,R,pl,mid);
	if(R>mid)update(rs(p),L,R,mid+1,pr);
	pushup(p);
}
ll query(ll p,ll L,ll R,ll pl,ll pr){
	if(L<=pl&&R>=pr){
		return sum[p];
	} 
	pushdown(p,pl,pr);
	ll res=0;
	ll mid=(pl+pr)>>1;
	if(L<=mid)res+=query(ls(p),L,R,pl,mid);
	if(R>mid)res+=query(rs(p),L,R,mid+1,pr);
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int c,a,b;
		cin>>c>>a>>b;
		if(c){
			cout<<query(1,a,b,1,n)<<endl;
		}else{
			update(1,a,b,1,n);
		}
	}
	return 0;
}

洛谷P6492

sum[]表示这个区间中最长的满足要求的连续子串的长度 suml[]表示这个区间中前缀满足要求的连续子串的长度
sumr[]表示这个区间中后缀满足要求的连续子串的长度

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
const int N=200005;
bool a[N];
ll n,q;
ll sum[N<<2],suml[N<<2],sumr[N<<2];
void build(ll p,ll pl,ll pr){
	sum[p]=suml[p]=sumr[p]=1;
	if(pl==pr)return;
	ll mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
}
void pushup(ll p,ll pl,ll pr){
	ll mid=(pl+pr)>>1;
	ll L=mid-pl+1,R=pr-mid;
	sum[p]=max(sum[ls(p)],sum[rs(p)]);
	suml[p]=suml[ls(p)],sumr[p]=sumr[rs(p)];
	if(a[mid]!=a[mid+1]){
		sum[p]=max(sum[p],sumr[ls(p)]+suml[rs(p)]);
		if(suml[ls(p)]==L)suml[p]=L+suml[rs(p)];
		if(sumr[rs(p)]==R)sumr[p]=R+sumr[ls(p)];
	} 
}
void update(ll p,ll x,ll pl,ll pr){
	if(pl==pr&&pl==x){
		a[pl]=!a[pl];
		return;
	}
	ll mid=(pl+pr)>>1;
	if(x<=mid)update(ls(p),x,pl,mid);
	else update(rs(p),x,mid+1,pr);
	pushup(p,pl,pr);
}
int main(){
	cin>>n>>q;
	build(1,1,n);
	for(int i=1;i<=q;i++){
		ll x;
		cin>>x;
		update(1,x,1,n);
		cout<<sum[1]<<endl;
	}
	return 0;
}

更新ing