在数轴上进行一系列操作。每次操作有两种类型,一种是在线段[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了啊