很基础的线段树题目。在范围[1,10000000]内依次覆盖n段区间[ai,bi]，问最后未被完全覆盖的区间共有多少个。
做的时候参考了http://bbs.byr.cn/#!article/ACM_ICPC/71462。关键是对每个结点要设置tag记录是否为叶子，每次拆分时，叶子结点的值继承被拆结点的值，并将tag设置为1。插入每段区间时，根据区间和结点之间的上下界关系进行相应处理即可。最后全部插入完毕后，用DFS查找值有效的叶子结点种类数目：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<cstdio> #include<cstring> struct node { char b; int d; node *l,*r; }mem[10000000],*root; int n,cnt,ml; char c[10001]; void calc(int l,int r,int L,int R,node *p,int e) { int j,k,m; if(l==L&&r==R) { p->b=1; p->d=e; return; } m=L+R>>1; if(p->b) { p->b=0; if(!p->l) { p->l=&mem[ml++]; p->l->l=p->l->r=0; } p->l->b=1; p->l->d=p->d; if(!p->r) { p->r=&mem[ml++]; p->r->l=p->r->r=0; } p->r->b=1; p->r->d=p->d; } if(r<=m) calc(l,r,L,m,p->l,e); else if(l>=m+1) calc(l,r,m+1,R,p->r,e); else { calc(l,m,L,m,p->l,e); calc(m+1,r,m+1,R,p->r,e); } } void DFS(node *p) { if(p->b) { if(!c[p->d]) { cnt++; c[p->d]=1; } } else { DFS(p->l); DFS(p->r); } } int main() { int i,j,k; scanf("%*d"); while(~scanf("%d",&n)) { cnt=0; ml=0; root=&mem[ml++]; root->b=1; root->d=0; root->l=root->r=0; for(i=1;i<=n;i++) { scanf("%d%d",&j,&k); calc(j,k,1,100000000,root,i); } memset(c,0,sizeof c); c[0]=1; DFS(root); printf("%d\n",cnt); } return 0; } |