P1856 矩形周长

哇！这小破题坑了我好久。

扫描线＋线段树

这题数据范围小，没离散化。真要离散化我还搞不好呢。

具体的看这个博客吧。

主要是这个坑爹的c，len把我搞了，其他的还好。

代码：

 #include <cstdio>

 #include <queue>

 #include <cmath>

 using namespace std;

 struct Node

 {

     int len,s;

 } node[];

 struct Edge

 {

     int L,R,high,flag;

     bool operator < (const Edge &a) const

     {

         if(this->high!=a.high)return this->high>a.high;

         return this->flag<a.flag;

     }

 };

 priority_queue<Edge>x;

 priority_queue<Edge>y;

 void build(int l,int r,int o)

 {

     node[o].len=;

     node[o].s=;

     if(l==r) return;

     int mid=(l+r)>>;

     build(l,mid,o<<);

     build(mid+,r,o<<|);

     return;

 }

 void up(int l,int r,int o)

 {

     if(node[o].s) node[o].len=r-l+;

     else if(l==r) node[o].len=;

     else node[o].len=node[o<<].len+node[o<<|].len;

     return;

 }

 void add(int L,int R,int v,int l,int r,int o)

 {

     //printf("add:%d %d %d %d %d %d\n",L,R,v,l,r,o);

     if(L<=l && r<=R)

     {

         node[o].s+=v;

         up(l,r,o);

         return;///这里的return一开始忘了打，死循环。

     }

     if(R<l || r<L) return;

     int mid=(l+r)>>;

     if(L<=mid) add(L,R,v,l,mid,o<<);

     if(mid<R)  add(L,R,v,mid+,r,o<<|);

     up(l,r,o);

     return;

 }

 void adde(int x1,int y1,int x2,int yyy)

 {

     Edge xup,xlow,yup,ylow;

     xup.L=xlow.L=ylow.high=x1;

     xup.R=xlow.R=yup.high=x2;

     yup.L=ylow.L=xlow.high=y1;

     yup.R=ylow.R=xup.high=yyy;

     xlow.flag=ylow.flag=;

     xup.flag=yup.flag=-;

     //printf("adde:%d %d %d %d\n",xup.L,xup.R,xup.high,xup.flag);

     //printf("adde:%d %d %d %d\n",xlow.L,xlow.R,xlow.high,xlow.flag);

     x.push(xup);

     x.push(xlow);

     y.push(yup);

     y.push(ylow);

     return;

 }

 int main()

 {

     int N = ;

     build(,N,);

     int n,x1,x2,y1,yyy;

     scanf("%d",&n);

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

     {

         scanf("%d%d%d%d",&x1,&y1,&x2,&yyy);///这里 的变量名传错了，0分

         adde(x1+,y1+,x2+,yyy+);

     }

     Edge e;int len=;

     long long int ans=;

     while(!x.empty())

     {

         //printf("x\n");

         e=x.top();

         x.pop();

         //printf("edge:%d %d %d %d\n",e.L,e.R,e.high,e.flag);

         add(e.L,e.R-,e.flag,,N,);

         ans+=abs(node[].len-len);

         len=node[].len;

         //printf("ans=%d\n",ans);

     }

     build(,N,);len=;

     while(!y.empty())

     {

         //printf("y\n");

         e=y.top();

         //printf("edge:%d %d %d %d\n",e.L,e.R,e.high,e.flag);

         y.pop();

         add(e.L,e.R-,e.flag,,N,);

         ans+=abs(node[].len-len);

         len=node[].len;

         //printf("ans=%d\n",ans);

     }

     printf("%lld",ans);

     return ;

 }

 /**

 4

 1 1 2 2

 3 1 5 3

 4 0 6 2

 5 -1 7 1

 20

 */

洛谷的数据好水

还有更高级的方法我没搞了，晦涩难懂......