学步园

虽然是过，其实我也没想会过，这样做竟不超时，有点厉害

不过也有点慢了，回来再做过

我用了lazy思想，由于每次都要tree_search使得其很慢，网上有些代码是

增加记录域ylenonce,ylenmore分别是记录覆盖一次的长度，覆盖二次以上的长度

这样就不要tree_searh了，快了不知多少~~~

我的代码：

#include<iostream><br /> #include<cmath><br /> #include<cstdlib><br /> #define N 1005</p> <p>using namespace std;</p> <p>struct elem{<br /> double x;<br /> double ly;<br /> double ry;<br /> bool flag;<br /> };</p> <p>struct node{<br /> int l;<br /> int r;<br /> double m;<br /> int cover;<br /> bool flag1;<br /> };</p> <p>elem cor[2*N];<br /> node tree[8*N];<br /> double index[2*N];<br /> int len;<br /> int n;<br /> double res;</p> <p>int cmp(const void *a,const void *b)<br /> {<br /> if((*(elem*)a).x > (*(elem *)b).x)<br /> return 1;<br /> else if((*(elem*)a).x == (*(elem *)b).x)<br /> return 0;<br /> else<br /> return -1;<br /> }</p> <p>int cmp1(const void *a,const void *b)<br /> {<br /> if(*(double *)a > *(double *)b)<br /> return 1;<br /> else if(*(double *)a == *(double *)b)<br /> return 0;<br /> else<br /> return -1;<br /> }</p> <p>void init()<br /> {<br /> int i;<br /> int k;<br /> double x1,y1,x2,y2;<br /> scanf("%d",&n);<br /> for(i = 0;i < n;i++){<br /> scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);<br /> k = i<<1;<br /> cor[k].x = x1; cor[k].ly = y1; cor[k].ry = y2;<br /> cor[k].flag = true;<br /> cor[k+1].x = x2; cor[k+1].ly = y1; cor[k+1].ry = y2;<br /> cor[k+1].flag = false;<br /> index[k] = y1; index[k+1] = y2;<br /> }<br /> qsort(cor,2*n,sizeof(cor[0]),cmp);<br /> qsort(index,2*n,sizeof(index[0]),cmp1);<br /> len = 0;<br /> for(i = 1;i < 2*n;i++){<br /> if(index[i] != index[i-1])<br /> index[++len] = index[i];<br /> }<br /> return ;<br /> }</p> <p>int find(double x)<br /> {<br /> int mid;<br /> int base = 0,top = len;<br /> while(base <= top){<br /> mid = (base+top)/2;<br /> if(x < index[mid])<br /> top = mid-1;<br /> else if(x > index[mid])<br /> base = mid+1;<br /> else return mid;<br /> }<br /> return -1;<br /> }</p> <p>void buid_tree(int k,int left,int right)<br /> {<br /> int mid;<br /> int L,R;<br /> tree[k].l = left; tree[k].r = right;//if(tree[k].l == 4 && tree[k].r == 5) cout <<"k:" <<k <<endl;<br /> tree[k].m = 0; tree[k].cover = 0; tree[k].flag1 = false;<br /> if(tree[k].r-tree[k].l == 1)<br /> return ;<br /> mid = (tree[k].l+tree[k].r)/2;<br /> L = k<<1; R = L+1;<br /> buid_tree(L,left,mid);<br /> buid_tree(R,mid,right);<br /> return ;<br /> }</p> <p>void init_m(int k)<br /> {<br /> int L,R;<br /> if(tree[k].cover >= 2){<br /> tree[k].m = index[tree[k].r]-index[tree[k].l];<br /> return ;<br /> }<br /> L = k<<1; R = L+1;<br /> if(tree[k].r-tree[k].l > 1){<br /> tree[k].m = tree[L].m+tree[R].m;<br /> return ;<br /> }<br /> tree[k].m = 0;<br /> return ;<br /> }</p> <p>void tree_insert(int k,int left,int right)<br /> {<br /> int mid;<br /> int L,R;<br /> if(left <= tree[k].l && right >= tree[k].r){<br /> tree[k].cover++;//cout <<'(' <<tree[k].l <<',' <<tree[k].r <<',' <<tree[k].cover <<") ";<br /> //init_m(k);<br /> tree[k].flag1 = true;<br /> return ;<br /> }<br /> mid = (tree[k].l+tree[k].r)/2;<br /> L = k<<1; R = L+1;<br /> if(tree[k].cover){<br /> tree[L].cover += tree[k].cover;<br /> tree[R].cover += tree[k].cover;<br /> tree[k].cover = 0;<br /> }<br /> if(left < mid) tree_insert(L,left,right);<br /> if(right > mid) tree_insert(R,left,right);<br /> //init_m(k);<br /> return ;<br /> }</p> <p>void tree_delete(int k,int left,int right)<br /> {<br /> int mid;<br /> int L,R;//if(tree[k].l == 4 && tree[k].r == 5)cout <<"dgd:" <<tree[k].cover <<endl;<br /> if(left <= tree[k].l && right >= tree[k].r){<br /> tree[k].cover--;<br /> tree[k].flag1 = true;<br /> //init_m(k);<br /> return ;<br /> }<br /> mid = (tree[k].l+tree[k].r)/2;<br /> L = k<<1; R = L+1;<br /> if(tree[k].cover){<br /> tree[L].cover += tree[k].cover;<br /> tree[R].cover += tree[k].cover;<br /> tree[k].cover = 0;<br /> }<br /> if(left < mid) tree_delete(L,left,right);<br /> if(right > mid) tree_delete(R,left,right);<br /> //init_m(k);<br /> return ;<br /> }</p> <p>void tree_search(int k)<br /> {<br /> int L,R; </p> <p> if(tree[k].cover > 1){<br /> //init_m(k);<br /> tree[k].m = index[tree[k].r]-index[tree[k].l];//cout <<tree[k].r <<'-' <<tree[k].l << ' ';<br /> return ;<br /> }<br /> if(tree[k].r-tree[k].l == 1){<br /> tree[k].m = 0;<br /> return ;<br /> }<br /> L = k<<1; R = L+1;<br /> if(tree[k].cover){<br /> tree[L].cover += tree[k].cover;<br /> tree[R].cover += tree[k].cover;<br /> tree[k].cover = 0;<br /> }<br /> tree_search(L);<br /> tree_search(R);<br /> //init_m(k);<br /> tree[k].m = tree[L].m+tree[R].m;<br /> return ;<br /> }</p> <p>int main()<br /> {<br /> int tcase;<br /> int i;int l,r;<br /> scanf("%d",&tcase);<br /> while(tcase--){<br /> init();<br /> buid_tree(1,0,len);<br /> res = 0;<br /> for(i = 0;i < (2*n-1);i++){<br /> l = find(cor[i].ly); r = find(cor[i].ry);<br /> if(cor[i].flag){<br /> tree_insert(1,l,r);<br /> }<br /> else<br /> tree_delete(1,l,r);<br /> tree_search(1);<br /> res += tree[1].m*(cor[i+1].x-cor[i].x);<br /> }<br /> printf("%.2lf/n",res);<br /> }<br /> return 0;<br /> }