首页 > 其他分享 >P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

时间:2024-11-10 22:08:31浏览次数:4  
标签:二分 ch R2 yyOI int LL mid T1 include

P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

实际上整理整理没什么难的。主要是考数据结构,完了时间复杂度 \(O(n\log^2n)\) 的树状数组 + 二分,比 \(O(n\log n)\) 的线段树上二分还快,而且线段树还差 20ms 就爆了,线段树还是得优化常数。

通过推公式,二分找出经过 k 轮(全部都使用),能把血量清零。然后 k - 1, 去找最后一轮实际上用多少,这里主要是求 sum 与 二分,所以可以使用线段树上二分,或者树状数组求和 + 二分。

附上测评结果:
树状数组: 记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
线段树(不卡常):记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
线段树(卡常):记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树状数组 + 二分

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long LL;

const int N = 200010;

LL n, m, w;
LL tr[N], trs[N];
LL a[N];


LL read()
{
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if(ch == '-' )
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch -'0', ch = getchar();
    return x * f;
}

int lowbit(int x)
{
    return x & -x;
}

void add(LL tr[], int x, LL k)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}

void addd(int l, int r, LL k)
{
    add(tr, l, k);
    add(tr, r + 1, -k);
    add(trs, l, l * k);
    add(trs, r + 1, -(r + 1) * k);
}


LL sum(LL tr[], int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL ssum(int x)
{
    LL a = sum(tr, x), b = sum(trs, x);
    return (__int128)a * (x + 1) - b;
}

LL find(LL x, LL sum)
{
    LL l = 0, r = 61;
    
    while (l < r)
    {
        LL mid = l + r >> 1;
        if ((__int128)sum * ((1ll << mid) - 1) >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

LL find2(LL w, LL k)
{
    int l = 0, r = n;
    
    while (l < r)
    {
        int mid = l + r >> 1;
        if ((__int128)ssum(mid) * (1ll << k) >= w) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main()
{
// 	freopen("wxyt4.in", "r", stdin);
// 	freopen("wxyt4.out", "w", stdout);

    cin >> n >> m >> w;
    
    for (int i = 1; i <= n; i ++ )
    {
        a[i] = read();
        add(tr, i, a[i] - a[i - 1]);
        add(trs, i, 1ll * i * (a[i] - a[i - 1]));
    }
    
    LL last = ssum(n);
    while (m -- )
    {
        LL l, r, d;
        l = read();
        r = read();
        d = read();
        addd(l, r, d);
        last += (r - l + 1) * d;
        LL res = last, ans = 0;
        LL k = find(w, res) - 1;
        ans = k * n; 
        ans += find2(w - res * ((1ll << k) - 1), k) - 1;
        printf("%lld\n", ans);
    }
    
    return 0;
}

线段树上二分

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>


using namespace std;

typedef long long LL;

const int N = 200010;

LL n, m, w;
LL a[N];

struct Node 
{
    int l, r;
    __int128 sum, add;
}tr[N * 4];

LL read()
{
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if(ch == '-' )
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch -'0', ch = getchar();
    return x * f;
}


void pushup(Node &u, Node &l, Node &r)
{
    u = {l.l, r.r, l.sum + r.sum};
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(Node &u, LL add)
{
    u.sum += (u.r - u.l + 1) * add;
    u.add += add;
}

void pushdown(int u)
{
    pushdown(tr[u << 1], tr[u].add);
    pushdown(tr[u << 1 | 1], tr[u].add);
    tr[u].add = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, a[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add)
{
    if (l <= tr[u].l && tr[u].r <= r) pushdown(tr[u], add);
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, add);
        if (r > mid) modify(u << 1 | 1, l, r, add);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL sum = 0;
        if (l <= mid) sum += query(u << 1, l, r);
        if (r > mid) sum += query(u << 1 | 1, l, r);
        return sum;
    }
}

LL findl(int u, int l, int r, LL k, LL w, LL sum)
{
    if (tr[u].l == tr[u].r) 
    {
        if ((__int128)(tr[u].sum + sum) * k < w) return -1;
        return tr[u].l;
    }
    else if (l <= tr[u].l && tr[u].r <= r)
    {
    	pushdown(u);
        if ((__int128)(tr[u << 1].sum + sum) * k >= w) return findl(u << 1, l, r, k, w, sum);
        else return findl(u << 1 | 1, l, r, k, w, sum + tr[u << 1].sum);
    }
}

LL find(LL x, LL sum)
{
    LL l = 0, r = 61;
    
    while (l < r)
    {
        LL mid = l + r >> 1;
        if ((__int128)sum * ((1ll << mid) - 1) >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

signed main()
{
//  	freopen("wxyt4.in", "r", stdin);
//  	freopen("wxyt4.out", "w", stdout);

    cin >> n >> m >> w;
    
    for (int i = 1; i <= n; i ++ )
    {
        a[i] = read();
    }
    
    build(1, 1, n);
    LL last = query(1, 1, n);
    while (m -- )
    {
        LL l, r, d;
        l = read();
        r = read();
        d = read();
        modify(1, l, r, d);
        last += 1ll * (r - l + 1) * d;
        LL res = last, ans = 0;
        LL k = find(w, res) - 1;
        ans = k * n; 
        ans += findl(1, 1, n, (1ll << k), w - res * ((1ll << k) - 1), 0) - 1;
        printf("%lld\n", ans);
    }
    
    return 0;
}

标签:二分,ch,R2,yyOI,int,LL,mid,T1,include
From: https://www.cnblogs.com/blind5883/p/18538631

相关文章

  • 电脑提示xinput1_3.dll丢失怎么解决,分享6种有效的解决方法
    xinput1_3.dll是一个动态链接库(DLL)文件,它在Windows操作系统中扮演着重要的角色,特别是在处理游戏控制器和其他输入设备的交互方面。这个文件是MicrosoftDirectX软件包的一部分,DirectX是微软公司开发的一个多媒体编程接口集,广泛应用于PC游戏开发中,以实现高效的图形渲染、音频处......
  • 电脑提示xinput1_3.dll丢失怎么办?游戏DLL修复方法详解
    xinput1_3.dll是一个动态链接库(DLL)文件,它在Windows操作系统中扮演着重要的角色,特别是在处理游戏控制器和其他输入设备的交互方面。这个文件是MicrosoftDirectX软件包的一部分,DirectX是微软公司开发的一个多媒体编程接口集,广泛应用于PC游戏开发中,以实现高效的图形渲染、音频处......
  • STM32+阿里云+ESP8266+MQTT+DHT11
    一、阿里云平台环境搭建注册完账号以后,找到控制台->物联网平台。    1.创建一个公共实例,若该实例有ID则为新公共实例2.创建一个产品[如何在物联网平台创建产品_物联网平台(IoT)-阿里云帮助中心(aliyun.com)](https://help.aliyun.com/zh/iot/user-guide/create......
  • 雅思口语part1-20题
    Doyouworkorstudy?"I’mcurrentlystudyingforamaster’sdegreeinArtificialIntelligence.Ireallyenjoythechallengesthatcomewithmystudies,especiallywhenitinvolvesworkingonreal-worldprojectsthathavepracticalapplications.&qu......
  • GA/T1400视图库平台EasyCVR多品牌摄像机视频平台前端监控摄像头镜头的基础知识
    在现代安全监控系统中,摄像机镜头作为捕捉图像的关键组件,其选择和应用直接影响到监控图像的质量和系统的整体性能。随着技术的发展,摄像机镜头的种类和功能也在不断扩展,以适应各种复杂的监控环境和需求。对于相机成像来讲,镜头是不可或缺的一部分,本篇文章在于帮助大家熟悉摄像机镜头......
  • CJ/T188-2004 详细介绍
    REDISANT提供互联网与物联网开发测试套件 #互联网与中间件:RedisAssistantZooKeeperAssistantKafkaAssistantRocketMQAssistantRabbitMQAssistantPulsarAssistantHBaseAssistantNoSqlAssistantEtcdAssistantGarnetAssistant工业与物联网:MQTTAssis......
  • CJ/T188-2004 报文举例
    REDISANT提供互联网与物联网开发测试套件 #互联网与中间件:RedisAssistantZooKeeperAssistantKafkaAssistantRocketMQAssistantRabbitMQAssistantPulsarAssistantHBaseAssistantNoSqlAssistantEtcdAssistantGarnetAssistant工业与物联网:MQTTAssi......
  • CJ/T188 调试工具介绍
    官网下载地址:CJ/T188主站模拟器功能介绍 #可用于任何厂商生产的符合CJ/T188标准的电能表。支持通过串口和TCP连接CJ/T188设备。支持CJ/T188-2004/2018协议。同时与多个水表通信。快速读取与写入数据,以表格形式展示,包含数据标识描述。完善且人性化的界面设计,带......
  • 中文汉化 数学计算软件:MATLAB R2023a 商业数学软件下载
    MATLABR2023a是由MathWorks公司推出的一款强大的数值计算和科学编程软件,广泛应用于工程、科学和数学领域。它提供了丰富的数值计算功能,包括线性代数、数值积分、微分方程等,并支持数据可视化、算法开发、深度学习和云服务集成等功能。用户可以使用MATLAB进行高效的矩阵运算、信号......
  • STM32之DHT11温湿度传感器
    DHT11是一款常用的单总线数字温湿度传感器,它能够提供相对湿度和温度的测量值。本文将详细介绍如何使用STM32微控制器读取DHT11传感器的数据。DHT11传感器特点湿度测量范围:20%~90%RH温度测量范围:0~50℃单总线数字输出低功耗易于安装和使用硬件连接DHT11传感器通常有三个......