HDU-5575-Discover Water Tank

ACM模版

描述

题解

左偏树可解。

初始默认所有 z=0z = 0 的情况,然后枚举 z=1z = 1 的情况来更新答案,并且可以用并查集来维护合并的水箱,既然水箱要合并,那么计算水箱的合并用可并堆比较快,可并堆中比较常用编码难度比较低的数到左偏树了。

这里由于需要向左向右进行查找挡板,合并后就忽视掉中间的挡板从而视作一个整体,所以仿真链式存储结构比较好。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5 + 10;
const int MAXM = 2e5 + 5;

int n, m, x, y, z, ans;
int L[MAXN], R[MAXN], LH[MAXN], RH[MAXN], O[MAXN], X[MAXN];
vector<pii> vp;

//  左偏树相关
int tot, v[MAXM], l[MAXM], r[MAXM], d[MAXM], Heap[MAXN];

//  合并左偏树
int merge(int x, int y)
{
    if (x == 0)
    {
        return y;
    }
    if (y == 0)
    {
        return x;
    }
    if (v[x] > v[y])
    {
        swap(x, y);
    }
    r[x] = merge(r[x], y);
    if (d[l[x]] < d[r[x]])
    {
        swap(l[x], r[x]);
    }
    d[x] = d[r[x]] + 1;
    return x;
}

//  初始化可并堆结点
inline int init(int x)
{
    v[++tot] = x;
    l[tot] = r[tot] = d[tot] = 0;
    return tot;
}

//  左偏树的插入操作
inline int insert(int x, int y)
{
    return merge(x, init(y));
}

//  取得左偏树中的最小值
inline int top(int x)
{
    return v[x];
}

//  弹出左偏树
inline int pop(int x)
{
    return merge(l[x], r[x]);
}

//  判断左偏树是否非空
inline bool empty(int x)
{
    return x == 0;
}

//  初始化可并堆
void initHeap()
{
    memset(Heap, 0, sizeof(Heap));
    tot = 0;
}

//  并查集相关
int p[MAXN];

//  初始化并查集
void initSet()
{
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
    }
}

//  查找集合的祖先
int find(int x)
{
    return x == p[x] ? x : p[x] = find(p[x]);
}

//  合并集合
inline void Union(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
    {
        return ;
    }
    p[y] = x;
    if (x < y)
    {
        RH[x] = RH[y];
        L[R[x]] = x;
        R[x] = R[y];
    }
    else
    {
        LH[x] = LH[y];
        R[L[x]] = x;
        L[x] = L[y];
    }
    //  合并可并堆
    Heap[x] = merge(Heap[x], Heap[y]);
    X[x] += X[y];
    O[x] += O[y];
}

int main()
{
    int T;
    scanf("%d", &T);

    for (int ce = 1; ce <= T; ce++)
    {
        scanf("%d%d", &n, &m);
        LH[1] = RH[n] = INT_MAX;
        L[n] = n - 1;
        for (int i = 1; i < n; i++)
        {
            scanf("%d", &RH[i]);
            //  用于快速查询水箱的左右挡板
            LH[i + 1] = RH[i];
            //  用于快速查询左右方水箱
            L[i] = i - 1;
            R[i] = i + 1;
        }

        initHeap();
        vp.clear();
        ans = 0;
        while (m--)
        {
            scanf("%d%d%d", &x, &y, &z);
            if (z == 1)
            {
                vp.push_back(pii(y + 1, x));
            }
            else
            {
                Heap[x] = Heap[x] ? insert(Heap[x], y) : init(y);
                ans++;
            }
        }

        initSet();
        sort(vp.begin(), vp.end());
        for (int i = 1; i <= n; i++)
        {
            O[i] = X[i] = 0;
        }
        for (int i = 0; i < vp.size(); i++)
        {
            x = find(vp[i].second);
            y = vp[i].first;
            //  向左溢出
            while (y > LH[x])
            {
                Union(x, L[x]);
                x = find(x);
            }
            //  向右溢出
            while (y > RH[x])
            {
                Union(x, R[x]);
                x = find(x);
            }
            //  删除水位以下的X
            while (!empty(Heap[x]) && top(Heap[x]) < y)
            {
                Heap[x] = pop(Heap[x]);
                X[x]++;
            }
            //  更新答案
            if (++O[x] >= X[x])
            {
                ans += (O[x] - X[x]);
                O[x] = X[x] = 0;
            }
        }

        printf("Case #%d: %d\n", ce, ans);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

Winform 中 DesignMode 返回值不正确的问题。

本文转载:http://blog.csdn.net/sabty/article/details/5325260

14410
来自专栏Fish

CUDA C最佳实践-CUDA Best Practices(二)

9. 内存优化 看页数也知道,内存优化是性能提升最重要的途径。目标在于通过最大化带宽获得对硬件的最大使用率。最好使用快速内存而减少慢速内存的访问。这章就是各种讨...

383100
来自专栏ACM小冰成长之路

51Nod-1833-环

ACM模版 描述 ? 题解 图论的问题我没有怎么深入学习,多数都是交给了队友去搞,所以看到这个题时,只知道是图上状压 DPDP,却不知道具体从何入手。 看了题解...

21060
来自专栏DOTNET

ASP.NET MVC编程——单元测试

1自动化测试基本概念 自动化测试分为:单元测试,集成测试,验收测试。 单元测试 检验被测单元的功能,被测单元一般为低级别的组件,如一个类或类方法。 单元测试要满...

55350
来自专栏ACM小冰成长之路

UVALive-7512-November 11th

ACM模版 描述 ? ? 题解 规律题。直接看代码吧,十分好理解。 代码 #include <cstdio> #include <iostream> #incl...

20350
来自专栏*坤的Blog

hdu1067

16240
来自专栏ACM小冰成长之路

51Nod-1661-黑板上的游戏

ACM模版 描述 ? 题解 很少见官方题解如此长篇大论(详细): ? 另外看到一个比较好的博客,讲得也十分详细,代码也十分的好,WildKid1024’s bl...

23480
来自专栏向治洪

android EventBus 3.0使用指南

Enventbus的作用和好处我就不多说了,这里介绍下怎么使用。 2.+版本的使用方法 public void onEvent(MessageEvent eve...

39750
来自专栏懒人开发

Eventbus3代码分析(四):@interface Subscribe分析

前面参考的代码,存放在(use_little_demo中的 eventbus3test) https://github.com/2954722256/use_...

13560
来自专栏后台开发+音视频+ffmpeg

dpvs源码分析(续)

在上一篇https://cloud.tencent.com/developer/article/1180256?s=original-sharing,我们已经介...

54710

扫码关注云+社区

领取腾讯云代金券