题解 P1904 【天际线】

· · 题解

看题解里没有人用分块？那就来一发分块的题解。

先将数据读入，再统计出建筑物的x坐标最大值，还要加一个1，否则就会没有最后两个输出。必须先读入，否则很难确定分块每块的大小。

然后就可以上我们的分块大法了。。。每扫一遍区间，然后再将不在整个块内的点全部暴力处理，再将每块标记上取最大值，最后统计该点的高度就是在数组内的高度和该点所在的块的标记的最大值。

最后判断将每一个点扫一遍，如果与前面的高度不一致，就输出该点的横坐标和高度。

时间复杂度为O(n \sqrt{n})，会比纯暴力快很多。

Code: 
#include <bits/stdc++.h>
#define maxn 10010
using namespace std;
int a[maxn],l[maxn],r[maxn],h[maxn],N,ln,rn;
int n,m,f[maxn];
template <typename T> void read(T &x) {
x = 0; char c = getchar();
for (; !isdigit(c); c = getchar());
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
}
int main() 
{
n=0;m=1;
while (scanf("%d",&l[m])!=EOF) //先读入
  {
    read(h[m]);read(r[m]);
    r[m]--;
    n=max(n,r[m]); //统计横坐标的最大值
    m++;
  }
m--;
n++; //最大横坐标要加一哦
N=sqrt(n);
for (int j=1;j<=m;j++)
  {
    ln=(l[j]-1)/N+1; 
    rn=(r[j]-1)/N+1; //将两个点所在的块找出来
    if (ln==rn)//分块大法不解释
      {
        for (int i=l[j];i<=r[j];i++)
          a[i]=max(a[i],h[j]);
        continue;
        }
    if (l[j]!=(ln-1)*N+1)
      {
        for (int i=l[j];i<=ln*N;i++)
          a[i]=max(a[i],h[j]);
        ln++;
      }
    if (r[j]!=rn*N)
      {
        for (int i=(rn-1)*N+1;i<=r[j];i++)
          a[i]=max(a[i],h[j]);
        rn--;
      }
    for (int i=ln;i<=rn;i++)
      f[i]=max(f[i],h[j]);
  }
int flag=0;
for (int i=1;i<=n;i++)
  {
    a[i]=max(a[i],f[(i-1)/N+1]);   //该点的高度就是在数组内的高度和该点所在的块的标记的最大值
    if (a[i]!=a[i-1])
        {
        if (flag==0) 
          printf("%d %d",i,a[i]);
        else printf(" %d %d",i,a[i]);
        flag=1;
        }
  }
printf("\n");
return 0;
}