Scan lines are generally used on graphics. It is very similar to its literal meaning, that is, a line sweeps across the entire graph. It is generally used to solve problems such as the area and perimeter of graphics. Let's take an example question as an example. Given n squares, these squares are placed overlapping each other in the plane Cartesian coordinate system, but all four sides are parallel to the coordinate axis, as shown in the figure below. So now that you know the topic, how do you apply it? First of all, we need to know how to use violence to solve this problem. According to the picture, the area in the picture is SABCD+SHEFG-SIDJE. Violent search is a good thing, but what should we do when the data range is large? Here we talk about scan lines.
Figure 1 Scan line 1
Figure 2 Scan line 2
For this example question, the scanning line can be abstracted as these four purple straight lines (as shown in the picture above l1, l2, l3, l4). If you look closely, you can see that these four lines divide this figure into three rectangles. Then we can directly calculate the sum of these three rectangles, right? So now comes the difficulty, how to find the areas of these rectangles. We can convert the sides of the rectangle given in the question into straight lines (as shown below), that is, leaving only these four sides. These four lines are the core of the entire approach. Now that the four lines have been seen, we can see at a glance that the area is the ghost of the scan line from the beginning to the present minus the projection of the side of the rectangle that has ended and the distance between the two scan lines. Then add these products together.
Figure 3 Scan line 3
Figure 4 Scan line 4
Here’s how to implement it, first of all, we can think of using line segment trees to find the interval sum to find the length of these projections. So the interval is so large (-1e8~1e8), how can we build a tree? Won't space explode? Therefore, you should use a dynamic open point line segment tree. If you calculate that each scan line opens a node, then there are n nodes. There are a total of log21e8 layers, so it can be opened. According to this statement, each edge should be sorted. Since the scan is from left to right, the sorting should sort the abscissa from small to large, so each edge has three attributes: the position is the abscissa, starting from that point, ending from that point. These two points are the two endpoints of the ordinate.
struct Line
{ int from,to,x,val; }line[2001];
bool cmp1(const Line &a,const Line &b)
{ return a.x<b.x;
}
int main()
{ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); line[i*2-1].x=a; line[i*2-1].from=d+1; line[i*2-1].to=b; line[i*2-1].val=1; line[i*2].x=c; line[i*2].from=d+1; line[i*2].to=b; line[i*2].val=-1; } sort(line+1,line+1+2*n,cmp1);
} Let’s explain how to apply the line segment tree. We give each edge an attribute. The left side of the rectangle is defined as the incoming edge and given a value of +1. The right side is defined as the outgoing edge and given a value of -1. This is the meaning of val in the edge. So what does this have to do with the line segment tree? With this value, we can quickly assign a value directly to the line segment tree to show whether there are edges covering it, which is the meaning of the cover array in the code below. If the cover array has a value other than zero, then this interval has edges, that is, there is a contribution of r-l+1, otherwise there is none. This is the query. The leaf node must be found in the query, because there is no saying about uploading values or downloading values in the scan line.
int find(int l,int r,int p)
{ if(cover[p]) return sum[p]; if(lp==rp&&rp==0) return 0; int sum=0; if(lp!=0) sum+=find(l,(l+r)>>1,lp); if(rp!=0) sum+=find(((l+r)>>1)+1,r,rp); return sum;
} The most difficult thing is modification. If the current node is completely covered by the edge to be added, then just modify it directly. Otherwise, you need to recursively search for its son. If there is no son, dynamically open the node. Here is the idea of modification. Of course, don’t forget to modify the value of cover when modifying.
void change(int l,int r,int x,int y,int &p,int delta)
{ if(!p) p=++cnt; if(x<=l&&r<=y) { cover[p]+=delta; sum[p]=r-l+1; return; } int mid=(l+r)>>1; if(x<=mid) change(l,mid,x,y,lp,delta); if(y>mid) change(mid+1,r,x,y,rp,delta);
}
We use this code to think about a topic, which is bzoj1645 city skyline. We can know the fact of TLE, but why? Since we need to query every time, each query has a time complexity of at least O(n), so our overall time complexity is greater than O(n^2). We need to optimize it. We can open an array called sum, which means we can redefine the sum array above. Here We define the sum array as the sum of all the edges in the current interval, then we can easily know that if the cover value of the current interval is greater than zero, the sum array is located at r-l+1 of the current interval. If cover is equal to zero, the value of the sum array is equal to the sum of the sum array values of his left and right sons. Isn't it very simple? According to the definition of the line segment in the entire graphic and the sum value of the position. The following is the modified interval modification and pushup function. Of course, since we can find the sum of line segments in the entire graph in O(1), the find function is not available.
void pushup(int p,int l,int r)
{ if(cover[p]>0) sum[p]=r-l+1; else sum[p]=sum[lson[p]]+sum[rson[p]];
}
void change(int l,int r,int x,int y,int &p,int delta)
{ if(!p) p=++cnt; if(x<=l&&r<=y) { cover[p]+=delta; pushup(p,l,r); return; } int mid=(l+r)>>1; if(x<=mid) change(l,mid,x,y,lson[p],delta); if(y>mid) change(mid+1,r,x,y,rson[p],delta); pushup(p,l,r);
}