首页 > 其他分享 >洛谷-P10837 『FLA - I』云音泛

洛谷-P10837 『FLA - I』云音泛

时间:2024-08-05 14:54:17浏览次数:14  
标签:node P10837 洛谷 index int sum1 sum0 seg FLA

Abstract

传送门
这题是线段树+离散化的典型例子。

Idea

题目要求我们求出在至多只改变一朵花种植时间的情况下,最多有多长的时间是有且只有一朵花开放的。种花可以视为给起始时间到中止时间的区间 +1 ,挖走一朵花,只用在原来的起始时间到中止时间的区间 -1,即可,自然的想到用线段树去维护这个过程,考虑到本题 m 的大小达到了 1e9 ,故而需要加一个离散化。

顺便一提,这个题和扫描线模板非常相似。

Code

#include <bits/stdc++.h>
#define int long long
int n, m;

namespace seg
{
    const int maxn = 10000000;
    struct Node
    {
        int sum1, sum0, l, r;
        bool work; // 标志这个节点是否被激活
    } node[maxn];
    int index[maxn];
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
#define m(l, r) (l + r >> 1)
    int lazy[maxn];
    void pushUp(int p)
    {
        if (lazy[p])
        {
            node[p].sum0 = 0;
            if (lazy[p] > 1)
            {
                node[p].sum1 = 0;
            }
            else
            {
                node[p].sum1 = node[l(p)].sum0 + node[r(p)].sum0;
            }
        }
        else
        {
            node[p].sum0 = node[l(p)].sum0 + node[r(p)].sum0;
            node[p].sum1 = node[l(p)].sum1 + node[r(p)].sum1;
        }
        return;
    }
    void build(int p, int l, int r)
    {
        node[p].work = 1;
        node[p].l = index[l], node[p].r = index[r];
        if (r - l > 1)
        {
            build(l(p), l, m(l, r));
            build(r(p), m(l, r), r);
            pushUp(p);
        }
        else
        {
            node[p].sum0 = node[p].r - node[p].l;
            node[p].sum1 = 0;
        }
        return;
    }

    void update(int p, int ql, int qr, int k)
    {
        int l = node[p].l, r = node[p].r;
        if (ql <= l && r <= qr)
        {
            lazy[p] += k;
            if (!node[l(p)].work)
            {
                if (lazy[p] > 1)
                {
                    node[p].sum0 = 0;
                    node[p].sum1 = 0;
                }
                else if (lazy[p] == 1)
                {
                    node[p].sum0 = 0;
                    node[p].sum1 = node[p].r - node[p].l;
                }
                else
                {
                    node[p].sum0 = node[p].r - node[p].l;
                    node[p].sum1 = 0;
                }
            }
            else
            {
                pushUp(p);
            }
        }
        if (node[l(p)].r > ql)
        {
            update(l(p), ql, qr, k);
        }
        if (node[r(p)].l < qr)
        {
            update(r(p), ql, qr, k);
        }
        pushUp(p);
        return;
    }
};

int t[seg::maxn];

signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        std::cin >> t[i];
        // 离散化处理
        seg::index[2 * i + 2] = t[i];
        seg::index[2 * i + 1] = t[i] + m;
    }
    std::sort(seg::index + 1, seg::index + 2 * n + 1);
    seg::build(1, 1, 2 * n);

    for (int i = 0; i < n; i++)
    {
        seg::update(1, t[i], t[i] + m, 1);
    }
    // 如果初识状态就已经是最大值,直接输出 ori_ans 即可
    int ori_ans = seg::node[1].sum1;
    int ans = -1e8;
    for (int i = 0; i < n; i++)
    {
        seg::update(1, t[i], t[i] + m, -1);
        ans = std::max(ans, seg::node[1].sum1);
        seg::update(1, t[i], t[i] + m, 1);
    }
    if (ori_ans >= ans + m)
    {
        std::cout << ori_ans;
    }
    else
    {
        std::cout << ans + m;
    }
    return 0;
}

标签:node,P10837,洛谷,index,int,sum1,sum0,seg,FLA
From: https://www.cnblogs.com/carboxylBase/p/18343205

相关文章

  • 洛谷P10839 【MX-J2-T0】Turtle and Equations题解
    灰常简单!蒟蒻带您写代码!题目理解题目传送门题目描述给你四个正整数。现在你有一条算式。你需要判断能否在两个方框内分别填入三种运算符 之一(运算符可以重复使用),使得算式运算的结果等于。题目分析分析后我们能够发现,只要一一列举出所有能够输出的情况,剩下的输出即可......
  • P10837 『FLA - I』云音泛
    原题链接题解修改玫瑰\(i\),对答案的影响是:减去只有玫瑰\(i\)的区间,加上只有玫瑰\(i\)和另一个玫瑰的区间,加上m因此我们对每个玫瑰\(i\),维护上述两个区间长度由于每个玫瑰开花时间一样,所以我们可以用扫描线的思想,对所有区间的端点离散化排序,然后升序遍历,由于开花时间......
  • 洛谷P1842 [USACO05NOV] 奶牛玩杂技
    [USACO05NOV]奶牛玩杂技题目背景FarmerJohn养了\(N\)头牛,她们已经按\(1\simN\)依次编上了号。FJ所不知道的是,他的所有牛都梦想着从农场逃走,去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳(她们还尝试过把自己装在大炮里发射......
  • 洛谷P4910题解
    题目大意现在穿T次手串,每根手串的长度分别为不同的n,有木和金两种珠子,相邻两颗珠子必须有一个是金。题目思路分析我们现在设穿到第n个珠子时用金的方案数为f[1][n],用木的方案数为f[0][n]如果第n个珠子为金,那么前一颗珠子是什么都可以,因此f[1][n]=f[1][n-1]+f[0][n-1]而如果......
  • Flask 应用程序的 POST 请求出现 405 method not allowed 错误
    我有一个简单的Web应用程序,可以使用以下代码向选定的受访者发送消息(使用TwilioAPI):app.pyclient=Client(account_sid,auth_token)@app.route('/')defindex():returnrender_template('index.html')@app.route('/send_sms',methods=['POST......
  • FLASK 相关链接
    FLASK中文文档:https://dormousehole.readthedocs.io/en/latest/FLASK教程:https://www.bookstack.cn/read/head-first-flask/README.mdhttp://www.coolpython.net/flask_tutorial/basic/route.htmlhttp://www.pythondoc.com/flask-mega-tutorial/index.htmlPython中文学......
  • python+flask计算机毕业设计健康管理系统的设计与实现(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景近年来,随着人们生活水平的提高和健康意识的增强,健康管理已成为社会关注的焦点。传统的健康管理方式往往依赖于纸质记录和医生的口头建议,这......
  • python+flask计算机毕业设计实验室信息化管理系统(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景在当今快速发展的科技时代,实验室作为科研与教学的核心场所,其管理效率和信息化水平直接影响到研究成果的质量和速度。传统的实验室管理方式......
  • python+flask计算机毕业设计中国诗词鉴赏网站(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景中国诗词作为中华文化的重要组成部分,承载着千年的历史与文化底蕴。从古至今,诗词一直是文人墨客表达情感、描绘景象的重要工具。然而,随着时......
  • python+flask计算机毕业设计装修公司管理系统(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景近年来,随着城市化进程的加速和人们生活水平的提高,装修行业迎来了前所未有的发展机遇。然而,传统装修公司管理方式存在诸多弊端,如信息不透明......