箱子Ⅱ_线段树

2019-11-08 01:03:34

字体：大中小

来源：转载

供稿：网友

题目描述

在一个1000米长的桌子上放着很多盒子，桌子的后方有一堵墙，如下图所示。假设人站得足够远，问：从桌子前方可以看到多少个盒子？

思路

用线段树记录一个值c=0为未完全覆盖，c>=1时每个数表示一种颜色，开一个f数组标记每种颜色是否出现过，就可以了 O(logn)

#include <stdio.h>struct tree{ int l,r,c;}t[1000];int fl[1000];int insert(int f,int x,int y,int i){ if (t[f].c==0) { int m=(t[f].l+t[f].r)/2; if (t[f].l==x&&t[f].r==y) t[f].c=i; else if (y<=m) insert(f*2,x,y,i); else if (x>=m) insert(f*2+1,x,y,i); else { insert(f*2,x,m,i); insert(f*2+1,m,y,i); } }}int count(int f){ if (t[f].c!=0) fl[t[f].c]=1; else if (t[f].r-t[f].l==0) return 0; else return count(f*2)+count(f*2+1);}int create(int f){ if (t[f].l!=t[f].r-1) { int m=(t[f].l+t[f].r)/2; t[f*2].l=t[f].l; t[f*2].r=m; t[f*2+1].l=m; t[f*2+1].r=t[f].r; create(f*2); create(f*2+1); }}int main(){ int n,m; scanf("%d%d",&n,&m); t[1].l=1; t[1].r=n; create(1); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); insert(1,x,y,i); } count(1); int ans=0; for (int i=1;i<=m;i++) if (fl[i]==1) ans++; PRintf("%d/n",ans);}

上一篇：合并排序数组

下一篇：杂记