UVALive 4108 SKYLINE

SKYLINE - UVALive 4108 - Virtual Judge (vjudge.net)

题目描述

我们要在第地平线上依次建造n座建筑，建筑物的修建按照从后往前的顺序，因此新建筑可能会挡住一部分

老建筑。修建完一座建筑之后统计它在多长的部分是最高的，并把这个长度称为该建筑的覆盖度，输出所有建筑的总覆盖度

样例

算法1

(线段树区间最大值及最大最小值 + 线段树二分)

分析：

首先我们必须要明确需要维护哪些信息
抽象的来说需要维护没有被覆盖掉的建筑物的高度
没有被覆盖掉的建筑的情况如图：

图片说明

我们发现上图中C建筑的信息是不需要维护的因为它已经被完全覆盖了，能被C覆盖的区间一定会被B覆盖，即使不会被C覆盖也有可能被B覆盖，所以在C建筑的区间我们值要维护B建筑的信息即可

图片说明

进一步观察我们发现一个区间的信息可能很复杂（中间红色竖线的部分），我们不可能维护区间中所有信息所以我们要维护一个代表信息，这个信息可以是最大值
然而仅仅是最大值还不够，最大值有可能是某个大区间的一小部分，新加入的建筑可能在这个区间的另外一部分是最大值
所以我们还需要知道这个区间可不可能存在使得新加入的建筑高度成为最大值的部分，所以我们可能还要维护一个“最小值”。
但是根据1的分析如果一个建筑在任何一个区间都被完全覆盖了他的信息就没用了，所以我们维护的是“一个区间中所有子区间最大值中的最小值”

注：这里看起来最大值似乎就不需要维护了，但是最大值的维护是时间复杂度的保障，后面会讲到

信息：

我们要维护两个信息区间最大值 $maxv$ ，一个区间中任意子区间最大值中的最小值 $minv$
由于是区间修改所以我们还要维护懒标记 $setv$

信息维护：

设区间 $d$ ,左区间 $ld$ ,右区间 $rd$

最大值
- $d.maxv = max(ld.maxv,rd.mxav)$
一个区间中任意子区间最大值中的最小值
- $d.maxv = max(ld.minv,rd.minv)$

保证时间复杂度

设新加入的建筑高度为 $k$ ,如果某个大区间 $d$ , $d.maxv <= k$ ,我们就不需要继续往下递归了，直接将这整个区间设置的 $d.minv = d.maxv = d.setv = k$ 然后返回
如果不维护最大值我们就需要递归到线段树的叶子节点再更新信息
本题的另一个优化就是如果 $d.minv >= k$ 那么新加入的建筑的信息就没有用了，可以直接结束递归了

初始化：

由于本题查询和操作输入的特殊性
有多组测试样例，每组测试样例的查询的最大范围都是 $10^5$
我们不可能在每一组测试样例都建一颗 $10^5$ 的线段树

所以我们要定义如下的初始化函数

int flag[N * 4];
int ks;
void init(int u)
{
    if(flag[u] == ks) return;//如果flag[u] == ks说明当前区间在本次样例已经初始化过了
    flag[u] = ks;//当前测试样例没有初始化过
    tr[u].minv = tr[u].maxv = 0;
    tr[u].setv = -1;
}

void pushdown(int u)
{
    if(tr[u].setv != -1)
    {
        init(lc);
        init(rc);
        ...
    }
}
void pushup(int u)
{
    init(lc);
    init(rc);
    ...
}
void modify(int u,int l,int r,int k)
{
    init(u);
    ...
}
int query(int u,int l,int r,int k)
{
    init(u);
    ...
}

在每次使用或者修改区间之前都要检查当前区间是否初始化过

时间复杂度 $O(nlogn)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
const int INF = 0x3f3f3f3f;
struct Node
{
    int l,r;
    int minv,maxv;
    int setv;
}tr[N * 4];
char str[50];
int a[N];
int qu[N],cnt;
int flag[N * 4];
int ks;
int n,q;

void init(int u)
{
    if(flag[u] == ks) return;
    flag[u] = ks;
    tr[u].minv = tr[u].maxv = 0;
    tr[u].setv = -1;
}

void pushup(int u)
{
    init(lc);
    init(rc);
    tr[u].minv = min(tr[lc].minv,tr[rc].minv);
    tr[u].maxv = max(tr[lc].maxv,tr[rc].maxv);
}

void pushdown(int u)
{
    if(tr[u].setv != -1)
    {
        init(lc);
        init(rc);
        tr[lc].minv = max(tr[lc].minv,tr[u].setv);
        tr[lc].maxv = max(tr[lc].maxv,tr[u].setv);
        tr[rc].minv = max(tr[rc].minv,tr[u].setv);
        tr[rc].maxv = max(tr[rc].maxv,tr[u].setv);
        tr[lc].setv = max(tr[lc].setv,tr[u].setv);
        tr[rc].setv = max(tr[rc].setv,tr[u].setv);
        tr[u].setv = -1;
    }
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = Node({l,r,0,0,-1});
        return;
    }
    int mid = (l + r) >> 1;
    tr[u] = Node({l,r});
    build(lc,l,mid);
    build(rc,mid + 1,r);
    pushup(u);
}

void modify(int u,int l,int r,int k)
{
    init(u);
    if(tr[u].minv > k) return;
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].minv = tr[u].setv = k;
        if(tr[u].maxv <= k)
        {
            tr[u].maxv = k;
            return;
        }
    }
    if(tr[u].l == tr[u].r) return;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(lc,l,r,k);
    if(r > mid) modify(rc,l,r,k);
    pushup(u);
}

int query(int u,int l,int r,int k)
{
    init(u);
    if(tr[u].minv > k) return 0;
    if(tr[u].l >= l && tr[u].r <= r && tr[u].maxv <= k) 
        return (tr[u].r - tr[u].l + 1);
    if(tr[u].l == tr[u].r) return 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0;
    if(l <= mid) res += query(lc,l,r,k);
    if(r > mid)  res += query(rc,l,r,k);
    pushup(u);
    return res;
}

void dfs(int u,int l,int r,int k)//debug
{
    // printf("%d %d %d\n",tr[u].l,tr[u].r,tr[u].maxv);
    if(tr[u].l >= l && tr[u].r <= r && tr[u].maxv <= k) 
    {
        printf("%d %d %d\n",tr[u].l,tr[u].r,(tr[u].r - tr[u].l + 1));
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid && tr[lc].minv <= k) dfs(lc,l,r,k);
    if(r > mid && tr[rc].minv <= k) dfs(rc,l,r,k);
}

void solve()
{
    build(1,1,N - 1);
    while(scanf("%d",&n) == 1,n)
    {
        while(n -- )
        {
            scanf("%d",&q);
            ks ++;
            LL res = 0;
            for(int i = 0;i < q;i ++)
            {
                int l,r,h;
                scanf("%d%d%d",&l,&r,&h);
                // printf("%d\n",query(1,l,r - 1,h));
                // dfs(1,l,r - 1,h);
                res += query(1,l,r - 1,h);
                modify(1,l,r - 1,h);
            }
            printf("%lld\n",res);
        }
    }
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}