P1382 题解

· · 题解

我发现一件可怕的事情，就是这道题并没有分块题解。

为啥跑了个次优解啊，但是卡不到最优解了。

思路：以矩形的横长为区间，宽度为值，维护出来之后就可以找到轮廓上的点了。

这种只用取最大值的应该优先考虑分块，好写而且（比线段树）常数小一点。

还是老套路，小块暴力取最大值，整块维护一个最大值的标记，最后查询的时候对当前点和所在块的标记取一个最大值即可得到当前位置的纵坐标。

注意值域很大但是 n 很小，所以可以用 map 离散化。

需要注意的是矩形覆盖的应该看作单位长度而不是点，所以假如一个矩形覆盖了轴上 [x,y] 这些点应该看作是覆盖了 [x,y-1] 这几条线段。

如何输出轮廓线上的点，可以考虑当前的的高度和上一个的高度的关系，如果不相等，把当前点的坐标放进去，如果相等，更新横坐标。

分析一下复杂度，不然太不靠谱了。

首先分块分两个部分：

  1. 对小块的暴力操作。由于我们每次至多对两块进行这样的操作，每块的块长都是 \Theta(\sqrt{n}) 的，所以整体仍然是 \Theta(\sqrt{n}) 级别。
  2. 对大块的区间操作，对一个大块操作的复杂度是常数级别的，由于一共只有 \Theta(\sqrt{n}) 块，所以这个也是 \Theta(\sqrt{n}) 的。

综上，分块单次操作复杂度是根号的，那么总的复杂度是 \Theta(n\sqrt{n}) 的。

预处理和统计答案是线性的。

离散化可以看作是循环套二分，是 \Theta(n\log n) 的。

所以我们的总的复杂度还是 \Theta(n\sqrt{n}) 的，不够优秀可以通过本题。

代码：

#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ;i <= (n) ;i += (x))
using namespace std ;
template < typename T > inline void read ( T &x ) {
    x = 0 ;
    bool flag (0) ;
    register char ch = getchar_unlocked () ;
    while (! isdigit (ch)) {
        flag = ch == '-' ;
        ch = getchar_unlocked () ;
    }
    while (isdigit (ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48) ;
        ch = getchar_unlocked () ;
    }
    flag ? x = -x : 0 ;
} 
const int N = 2e5 + 7 ;
const int M = 630 ;
int belong[N] ,n ,h[N] ,l_[N] ,r_[N] ,b[N] ,a[N] ,tot ,t ,l[M] ,r[M] ,cov[M] ;
inline void modify (int nowl ,int nowr ,int k) {
    int p = belong[nowl] ,q = belong[nowr] ;
    if (p == q) {
        f (i ,nowl ,nowr ,1) 
            a[i] = max (a[i] ,k) ;
        return ;
    }
    f (i ,nowl ,r[p] ,1) 
        a[i] = max (a[i] ,k) ;
    f (i ,p + 1 ,q - 1 ,1) 
        cov[i] = max (cov[i] ,k) ;
    f (i ,l[q] ,nowr ,1) 
        a[i] = max (a[i] ,k) ;
    return ;
} 
inline int query (int cur) {
    return max (a[cur] ,cov[belong[cur]]) ;
}
vector < pair < int ,int > > ans ;
int main () {
    read (n) ;
    f (i ,1 ,n ,1) {
        read (h[i]) ,read (l_[i]) ,read (r_[i]) ;
        b[++ tot] = l_[i] ,b[++ tot] = r_[i] ;
    }
    sort (b + 1 ,b + tot + 1) ;
    tot = unique (b + 1 ,b + tot + 1) - b - 1 ; // 一定要去重，不然会导致断档
    f (i ,1 ,n ,1) {
        l_[i] = lower_bound (b + 1 ,b + tot + 1 ,l_[i]) - b ;
        r_[i] = lower_bound (b + 1 ,b + tot + 1 ,r_[i]) - b ;
    }
    t = sqrt (tot) ; // 注意是对 tot 分块
    f (i ,1 ,t ,1) 
        l[i] = (i - 1) * t + 1 ,r[i] = i * t ;
    if (r[t] < tot) {
        t ++ ;
        l[t] = r[t - 1] + 1 ;
        r[t] = tot ;
    }
    f (i ,1 ,t ,1) {
        f (j ,l[i] ,r[i] ,1)
            belong[j] = i ;
    }
    f (i ,1 ,n ,1) 
        modify (l_[i] ,r_[i] - 1 ,h[i]) ;           
    ans.emplace_back (b[1] ,0) ;
    int las = 0 ;
    f (i ,1 ,tot - 1 ,1) {
        int v = query (i) ;
        if (v != las) {
            ans.emplace_back (make_pair (b[i] ,v)) ;
            ans.emplace_back (make_pair (b[i + 1] ,v)) ;
        } else 
            (* -- ans.end ()).first = b[i + 1] ; // vector 的 end 返回的是空，要找前一个位置才是结尾
        las = v ;
    }
    ans.emplace_back (make_pair (b[tot] ,0)) ;
    cout << ans.size () << '\n' ;
    for (int i = 0 ;i < ans .size () ;i ++) 
        cout << ans[i].first << ' ' << ans[i].second << '\n' ;
    return 0 ;
}