线段树10分求调!!!
查看原帖
线段树10分求调!!!
1015796
Lingyu_fly楼主2024/3/16 13:30
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m;
struct tr{
	int l,r,sum=0,vis=0;
}tree[N*4];
void pushup(int u){
	tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void build(int u,int l,int r){
	tree[u].l=l;tree[u].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void pushdown(int u){
	if(!tree[u].vis) return;
	tree[u<<1].sum=tree[u<<1].r-tree[u<<1].l+1-tree[u<<1].sum;
	tree[u<<1|1].sum=tree[u<<1|1].r-tree[u<<1|1].l+1-tree[u<<1|1].sum;
	if(!tree[u<<1].vis) tree[u<<1].vis=1;
	else tree[u<<1].vis=0;
	if(tree[u<<1|1].vis==0) tree[u<<1|1].vis=1;
	else tree[u<<1|1].vis=0;
	tree[u].vis=0;
}
void modify(int u,int l,int r){
	if(l<=tree[u].l&&tree[u].r<=r){
		tree[u].sum=tree[u].r-tree[u].l+1-tree[u].sum;
		if(!tree[u].vis) tree[u].vis=1;
		else tree[u].vis=0;
		return;
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) modify(u<<1,l,mid);
	if(mid<r) modify(u<<1|1,mid+1,r);
	pushup(u);
}
int query(int u,int l,int r){
	if(l<=tree[u].l&&tree[u].r<=r){
		return tree[u].sum;
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	int ans=0;
	if(l<=mid) ans+=query(u<<1,l,mid);
	if(mid<r) ans+=query(u<<1|1,mid+1,r);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	int c,a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&c,&a,&b);
		if(c==0){
			modify(1,a,b);
		}else if(c==1){
			printf("%d\n",query(1,a,b));
		}
	}
	return 0;
}
2024/3/16 13:30
加载中...