hud 1828参考答案

ymc 2009/4/9 hdu 1828 picture 线段树 参考99年国家队IOI论文集 题目大意： 给定n个边与坐标轴平行的矩形，求这些矩形的覆盖的形状的周长。 思想： 把所有矩形的左右边按x轴坐标从小大大排列，并且标记是左边还是右边，存在line[]中。 扫描矩形的所有y坐标，排列，按照这些y坐标切割y轴，得到2*n-1条线段，存在y[]中， 用这2*n-1条线段建立线段树，跟节点为tree[1]。 扫描矩形的所有x坐标，排列。放在x[1]到x[2n-1]， 并且x[0]=x[1](计算时不用考虑第一次特殊情况)。 扫描line[]，如果line[i]为左边，则插入线段树，否则从线段树中删除。 插入算法：线段line[i]插入到tree[p]中 如果line[i]完全覆盖tree[p]，插入到tree[p]的树根。 再考虑插入到tree[p]的左子树与右子树。 同时记录tree[p]的跟节点需要更新(update=false)

删除算法：从tree[p]中删除line[i] 如果tree[p]完全被line[i]覆盖，从树根中删除。 再考虑从左子树与又子树中删除。 同时记录跟节点需要更新。

更新算法：更新树tree[p] 若tree被完全覆盖(count>0) 则 len=tree[p]的代表的线段的长度

• 左右端点都被覆盖（父节点可能要用到这个信息） 包含的线段数lines为1。

否则

• len=左子树的len+又子树的len 左右端点的覆盖情况要看左子树的左端点和右子树的右端点。 包含的线段数lines为左子树和右子树的线段之和。（考虑中间的两段是否合成一段）

初始ans=0（周长）; 每次插入或者删除线段line[i]时，同时计算ans的增长。具体如下： ans+=tree[1].lines*2*(x[i+1]-x[i1]) ans+=2*(更新信息前后，tree[1]中测度差的绝对值) */ #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const int N=20000; struct Line //表示平行与y轴的边 {

• int y1,y2; int x; bool left;//是否为矩形的左边

  bool operator <(const Line t) const {

  • return x<t.x;

  }

}; struct Node//线段树的节点 { // int l,r;

• int count; //节点是被线段完全覆盖的次数 int len; //节点上线段的测度 int lines; //节点上所包含的线段的段数 int lcover,rcover; //节点的左右端点是否被覆盖 bool update; //节点是否更新过

}; Node tree[4*N]; Line line[2*N]; int x[2*N],y[2*N];//x，y轴上的分割点， int n; void Build(int p,int left,int right)//left，right为y轴上分割点的下标 {

• tree[p].count=0; tree[p].len=0; tree[p].lines=0; tree[p].lcover=0; tree[p].rcover=0; tree[p].update=true; if(left==right-1)//叶节点
  • return;
  int m=(left+right)/2; Build(2*p,left,m); Build(2*p+1,m,right);

} void Insert(int p,int l,int r,int y1,int y2) {

• if(y1<=y[l]&&y[r]<=y2)//覆盖整个树p {

  • tree[p].count++; tree[p].update=false; //return; 这里不能返回，不然WA
  } if(l==r-1)
  • return;
  int m=(l+r)/2;

  if(y1<y[m])//插入到左子树 {

  • tree[p].update=false; Insert(2*p,l,m,y1,y2);
  }

  if(y[m]<y2)//插入到右子树 {

  • tree[p].update=false; Insert(2*p+1,m,r,y1,y2);
  }

} void Delete(int p,int l,int r,int y1,int y2) {

• if(y1<=y[l]&&y[r]<=y2)//从跟中删除 {

  • tree[p].count--; tree[p].update=false; //return; 这里不能返回，不然WA
  } if(l==r-1)
  • return;
  int m=(l+r)/2;

  if(y1<y[m])//从左子树中删除 {

  • tree[p].update=false; Delete(2*p,l,m,y1,y2);
  }

  if(y[m]<y2)//从右子树中删除 {

  • tree[p].update=false; Delete(2*p+1,m,r,y1,y2);
  }

} void Update(int p,int l,int r) {

• if(tree[p].update)//剪枝，不然TLE
  • return;

  if(tree[p].count>0)//被完全覆盖 {

  • tree[p].len=y[r]-y[l]; tree[p].lcover=true; tree[p].rcover=true; tree[p].lines=1;
  } else if(l==r-1) //叶节点并且count==0 {
  • tree[p].len=0; tree[p].lcover=false; tree[p].rcover=false; tree[p].lines=0;
  } else//不是也节点并且没被完全覆盖 {
  • int m=(l+r)/2; Update(2*p,l,m);//更新子节点 Update(2*p+1,m,r); tree[p].len=tree[2*p].len+tree[2*p+1].len;//从子节点得到根节点的信息 tree[p].lcover=tree[2*p].lcover; tree[p].rcover=tree[2*p+1].rcover; tree[p].lines=tree[2*p].lines+tree[2*p+1].lines;

    if(tree[2*p].rcover&&tree[2*p+1].lcover)

    • tree[p].lines--;
  }

} void Init() {

• int x1,y1,x2,y2; int k;

  for(int i=1;i<=n;i++) {

  • scanf("%d%d%d%d",&x1,&y1,&x2,&y2); k=2*i-2; x[k+1]=x1;//预留x[0] x[k+2]=x2; y[k]=y1; y[k+1]=y2; line[k].y1=line[k+1].y1=y1; line[k].y2=line[k+1].y2=y2; line[k].x=x1; line[k].left=true; line[k+1].x=x2; line[k+1].left=false;

  } sort(x+1,x+2*n+1); x[0]=x[1];//在出入与删除时，不需要特殊处理第一个线段 sort(y,y+2*n); sort(line,line+2*n);

} void Solve() {

• int r=2*n-1; Build(1,0,r); int Lastlen=0; int ans=0;

  for(int i=0;i<2*n;i++)//对所有线段插入或者删除。因为x[0]==x[1]，直接处理 {

  • if(line[i].left)
    • Insert(1,0,r,line[i].y1,line[i].y2);
    else
    • Delete(1,0,r,line[i].y1,line[i].y2);
    ans+=tree[1].lines*2*(x[i+1]-x[i]);//上下边数*长度 Lastlen=tree[1].len; Update(1,0,r); ans+=fabs((float)Lastlen-tree[1].len);//左右边的长度
  } printf("%d\n",ans);

} int main() {

• while(scanf("%d",&n)!=EOF) {

  • if(n==0) {
    • printf("0\n"); continue;
    } Init(); Solve();
  }

}