洛谷 P1856 【Picture】

其实这道题根本不需要什么覆盖层数，直接排序+暴力就能跑出0ms（洛谷0ms，FZOJ 4ms）.

我们开一个数组highest，highest[i]存储[i, i+1)这条线段上所有已经搜过的矩形的最高的上边的高度。如果现在正在搜的矩形的最低边高于已经搜过的，则中间就会有一层没贴的，于是需要计入总周长。

怎么处理能使得搜到这个矩形时，所搜到的最高的上边的高度不再会覆盖掉这个矩形呢？其实只要根据矩形的下表面从下至上的顺序排序，这样就能保证以后搜到的矩形只会往上走，最高值只会越来越高，而不会突然又搜到下面的矩形，导致重复统计了。

时间复杂度O(n log n + n × (maxx - minx) + n × (maxy - miny))。如果加入离散，则最坏时间复杂度为O(n)。

详见代码：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 //每个矩形的数据

 struct data {

     int lx,rx; //该矩形最左侧的横坐标与最右侧的横坐标

     int ly,ry; //纵坐标同理

 };

 const int maxn=, maxx=;

 int n;

 data a[maxn+];

 int highest[maxx+]; //已搜到的最高矩形上边界的高度

 bool cmp_x(data x, data y) { return x.lx<y.lx; }

 bool cmp_y(data x, data y) { return x.ly<y.ly; }

 void kuaidu(int &p) {

     char c; int f=; p=;

     do { c=getchar(); if (c=='-') f=-; } while (c<''||c>'');

     do p=p*+c-'', c=getchar(); while (c>=''&&c<='');

     p*=f;

 }

 void init() {

     kuaidu(n);

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

         kuaidu(a[i].lx); kuaidu(a[i].ly); kuaidu(a[i].rx); kuaidu(a[i].ry);

         //使所有坐标变为正数

         a[i].lx+=; a[i].ly+=; a[i].rx+=; a[i].ry+=;

     }

 }

 int solve_x() {

     memset(highest,-,sizeof(highest));

     int ans=;

     //根据下底的高度，对所有矩形排序

     sort(a+,a++n,cmp_x);

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

         for (int j=a[i].ly; j<a[i].ry; j++) { //处理区间[j,j+1)

             //正在处理的矩形下边界高于已经搜到过的所有矩形的最高线

             //所以在这个区间中多了一个矩形，答案加上上下边的长度(2)

             if (highest[j]<a[i].lx) ans+=;

             //更新已搜到的矩形区间[j,j+1)的最高的线的高度

             if (highest[j]<a[i].rx) highest[j]=a[i].rx;

         }

     return ans;

 }

 //y轴同理

 int solve_y() {

     memset(highest,-,sizeof(highest));

     int ans=;

     sort(a+,a++n,cmp_y);

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

         for (int j=a[i].lx; j<a[i].rx; j++) {

             if (highest[j]<a[i].ly) ans+=;

             if (highest[j]<a[i].ry) highest[j]=a[i].ry;

         }

     return ans;

 }

 int main() {

     init();

     printf("%d\n",solve_x()+solve_y());

     return ;

 }