求助线段树类模板题
  • 板块学术版
  • 楼主Judgelight
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/14 19:10
  • 上次更新2023/10/28 03:45:27
查看原帖
求助线段树类模板题
461616
Judgelight楼主2022/4/14 19:10

在数轴上进行一系列操作。每次操作有两种类型,一种是在线段[a,b]上涂上颜色,另一种将[a,b]上的颜色擦去。 问经过一系列的操作后,有多少条单位线段[k,k+1]被涂上了颜色。

第一行,一个整数n,表示总的操作数 以后n行输入三个整数(n<=100000)。 第一个数为1表示涂色,0表示擦去。 第二、三个数表示线段[a,b]。

(1<=a<b<=200000)

输入样例1: 5 1 1 15 0 4 9 1 7 18 1 7 9 0 1 3 输入样例2: 4
1 1 8 0 4 8 1 7 8 0 1 3

#include<bits/stdc++.h>
using namespace std;
long long m;
struct Tree{
	long long l,r,sum,tag;
}tr[8000012];
void pushup(long long u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
	if(tr[u].tag==1)tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1;
	else tr[u<<1].sum=0;
	tr[u<<1].tag=tr[u].tag;
	if(tr[u].tag==1)tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1;
	else tr[u<<1|1].sum=0;
	tr[u<<1|1].tag=tr[u].tag;
	tr[u].tag=0;
}
void build(long long u,long long L,long long R){
	tr[u].l=L;
	tr[u].r=R;
	tr[u].tag=0;
	if(L==R)return ;
	long long mid=L+R>>1;
	build(u<<1,L,mid);
	build(u<<1|1,mid+1,R);
}
void modify(long long u,long long v,long long x,long long y){
	if(tr[u].tag)pushdown(u);
	if(tr[u].l>=x&&tr[u].r<=y){
		tr[u].tag=v;
		if(v==1)tr[u].sum=tr[u].r-tr[u].l+1;
		else tr[u].sum=0;
	}
	else{
		long long mid=tr[u].l+tr[u].r>>1;
		if(x<=mid&&y>=tr[u<<1].l)modify(u<<1,v,x,y);
		if(y>mid&&x<=tr[u<<1|1].r)modify(u<<1|1,v,x,y);
		pushup(u);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>m;
	build(1,1,200009);
	for(int i=1;i<=m;i++){
		long long xx,ll,rr;
		cin>>xx>>ll>>rr;
		if(xx==1)
			modify(1,xx,ll,rr);
		else modify(1,-1,ll,rr);
	}
	cout<<tr[1].sum;
	return 0;
}

样例全过为什么WA了啊

2022/4/14 19:10
加载中...