本文共 1045 字，大约阅读时间需要 3 分钟。
题目大意：给若干个矩形，统计重叠次数不为0的面积。
题目分析：维护扫描线的长度时，只需要只统计覆盖次数大于1的区间即可。这是个区间更新，不过不能使用懒标记，但是数据规模不大，不用懒惰标记仍可以AC。
代码如下：
# include # include # include # include # include # include using namespace std;# define mid (l+(r-l)/2)const int N=1000;void read(int &x){ x=0; char c; while((c=getchar())&&(c<'0'||c>'9')); x=c-'0'; while(c=getchar()){ if(c<'0'||c>'9') break; x=x*10+c-'0'; }}//*****************************************struct Node{ int c; double len;};struct Segment{ double x1,x2,y; int d;};Segment seg[N*2+5];map mp;vector v;Node tr[(N<<3)+5];bool comp(const Segment &s1,const Segment &s2){ return s1.y 1) tr[rt].len=v[r]-v[l-1]; else tr[rt].len=0; }else{ if(L<=mid) update(rt<<1,l,mid,L,R,d); if(R>mid) update(rt<<1|1,mid+1,r,L,R,d); pushUp(rt); }}int main(){ //freopen("in.txt","r",stdin); int T,n; read(T); while(T--) { read(n); v.clear(); mp.clear(); double x1,x2,y1,y2; for(int i=0;i
转载于:https://www.cnblogs.com/20143605--pcx/p/5750126.html