洛谷 p1047 校门外的树 线段树做法

时间:2023-03-08 22:15:15

非常easy,

注意一下它是两端开始,也就是说0的位置也有一棵树就好了

我由于太弱了,一道红题交了4,5遍

由于树的砍了就没了,lazy标记最大就是1;

直接贴代码吧

#include<bits/stdc++.h>

using namespace std;

inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
inline void write(int x) {if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int sum[400010],lazy[400010]; void build(int root,int l,int r){
if(l == r){
sum[root] = 1;
return ;
}
int mid = (l + r) >> 1;
int left = root << 1;
int right = left + 1;
build(left,l,mid);
build(right,mid + 1,r);
sum[root] = sum[left] + sum[right];
} void add(int root,int l,int r,int k){
if(k == 0)
return ;
if(lazy[root])
return ;
lazy[root] = 1;
sum[root] = 0;
return ;
} void putdown(int root,int l,int r){
if(lazy[root] == 0)
return ;
int mod = lazy[root] % 2; int mid = (l + r) >> 1;
add(root * 2,l,mid,mod);
add(root * 2 + 1,mid + 1,r,mod);
lazy[root] = 0;
return ;
} void change(int root,int l,int r,int x,int y){
if(l > y || r < x)
return ;
if(l >= x && r <= y){
add(root,l,r,1);
return ;
}
int mid = (l + r) >> 1;
putdown(root,l,r);
int left = root << 1;
int right = left + 1;
if(x <= mid) change(left,l,mid,x,y);
if(mid < y) change(right,mid + 1,r,x,y);
sum[root] = sum[left] + sum[right];
} int find(int root,int l,int r,int x,int y){
if(l >= x && r <= y){
return sum[root];
}
int mid = (l + r) >> 1,ans = 0;
int left = root << 1;
int right = left + 1;
putdown(root,l,r);
if(x <= mid) ans += find(left,l,mid,x,y);
if(mid < y) ans += find(right,mid + 1,r,x,y);
return ans;
} int main(){
int n,m;
cin >> n >> m;
build(1,1,n + 1);
for(int i = 1; i <= m;++i){
int y,z;
scanf("%d%d",&y,&z);
change(1,1,n + 1,y + 1,z + 1);
}
write(find(1,1,n + 1,1,n + 1));
cout<<endl;
return 0;
}