正題

---

題意

一塊長m的墻，有n個大小不同的盒子放在前面，求沒有被擋住的墻的總長度

---

解題思路

用線段樹，0表示有沒被遮擋的，1表示完全被遮擋，-1表示有遮擋的和沒遮擋的。然后記數(shù)。

---

代碼

#include<cstdio> using namespace std; struct xjq{int l,r;bool cover; }tree[400000]; int n,ll,rr,w,s; void build(int x,int a,int b)//建樹 {tree[x].l=a;tree[x].r=b;if (b-a==1) return;else{int m=(a+b)/2;build(x*2,a,m);build(x*2+1,m,b);} } void inster(int x,int a,int b)//插入 {if (tree[x].cover) return;if (tree[x].l==a && tree[x].r==b) //標(biāo)記{tree[x].cover=true;return;}int m=(tree[x].r+tree[x].l)/2;if (b<=m) inster(x*2,a,b);else if (a>=m) inster(x*2+1,a,b);else{inster(x*2,a,m);inster(x*2+1,m,b);}return; } void find(int x) {if (tree[x].cover)//完全被遮擋{s+=tree[x].r-tree[x].l;return;}if (tree[x].r-tree[x].l==1) return;else {find(x*2);find(x*2+1);return;} } int main() {scanf("%d",&w);scanf("%d",&n);build(1,1,w);for (int i=1;i<=n;i++){scanf("%d%d",&ll,&rr);inster(1,ll,rr);}s=0;find(1);printf("%d",s); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的ssl2644-线段树练习1【线段树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。