首页 > 其他分享 >P4231 三步必杀

P4231 三步必杀

时间:2024-02-02 16:47:47浏览次数:27  
标签:前缀 16 int ll 必杀 差分 P4231 数组 三步

原题链接

算是 差分 的进阶吧,这道题算是差分+差分的题目,即要两次差分再求前缀和。

先来解释原理:

给定一个数组a长度为n,初始都为0。接下来m个操作:
1、在l~r的范围上加上一个首项为s,末项为e的等差数列。
接着求出m次操作后数组a的各项值

例如【0,0,0,0,0,0,0,0,0,0】的数组

一次操作为在4~8的位置上加上首项为4,末项为16的等差数列。

看着像差分,但细想又不太一样,因为我们进行前缀和操作之前的数组a应该如下

【0,0,0,4,3,3,3,3,-16,0】,l~r位置上的值都变了,导致只用一次差分无法解决。

那么我们在观察一下发现上面这个数组可以根据【0,0,0,4,-1,0,0,0,-19,16】通过前缀和求得。

那么我们就可以通过一次差分+两次前缀和的方式来实现对数组的转化。

主要代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=3e5+5;
typedef long long ll;
ll a[N];
int l[M],r[M],s[M],e[M];
int n,m;
ll max_=0,pre=0;
void setbuild(){
    for (int i=1;i<=m;i++){
        int d=(e[i]-s[i])/(r[i]-l[i]);
        a[l[i]]+=s[i];
        a[l[i]+1]+=d-s[i];
        a[r[i]+1]-=d+e[i];
        a[r[i]+2]+=e[i];
    }
}
void build(){
    for (int i=1;i<=n;i++) a[i]+=a[i-1];
    for (int i=1;i<=n;i++){
        a[i]+=a[i-1];
        max_=max(max_,a[i]);
        pre^=a[i];
    }
}
int main(){
    ios::sync_with_stdio(false);  //由于输入量巨大,不加这一句会超时
    cin>>n>>m;
    for (int i=1;i<=m;i++) cin>>l[i]>>r[i]>>s[i]>>e[i];
    setbuild();
    build();
    cout<<pre<<" "<<max_;
    return 0;
}

 

标签:前缀,16,int,ll,必杀,差分,P4231,数组,三步
From: https://www.cnblogs.com/purple123/p/18003430

相关文章

  • “研学测”好帮手,三步带你安装体验TDH社区开发版
      星环科技TDH社区开发版,作为一款单机可部署、开箱即用的大数据基础平台产品,大幅降低了用户的资源成本和使用门槛。与此同时,TDH社区开发版兼顾此前TDH社区版(分布式)组件成熟、简单易用、易运维等特点,可以轻松、高效地完成科研教学、开发测试等数据分析需求。 “三步”安装......
  • Atlassian 停服 Bitbucket?三步快速迁移至极狐GitLab
    之前的文章Jira母公司全面停服Server产品,用户如何迁移至极狐GitLab提到了Atlassian将在2月15日以后停止对Server端产品的服务支持,此后用户将无法像之前一样继续使用Jira、Bitbucket、Bamboo、Confluence这些产品了。如果用户想要继续使用这些产品,就需要迁移到Atlass......
  • 云图说|有了这2招必杀技,你的主机“身陷重围”都不怕!
    阅识风云是华为云信息大咖,擅长将复杂信息多元化呈现,其出品的一张图(云图说)、深入浅出的博文(云小课)或短视频(云视厅)总有一款能让您快速上手华为云。更多精彩内容请单击此处。摘要:华为云主机安全服务HSS在2023年12月推出了全新版本,新增包括应急漏洞防护、全盘病毒查杀等功能,......
  • 搭建lnmp环境-nginx关联php-fpm (第三步)
     永久关闭防火墙sudosystemctlstopfirewalldsudosystemctldisablefirewall 安装php扩展 php-fpmyum-y installphp-fpm systemctlstart php-fpm.servicesystemctlenable php-fpm.service  修改php-fpm用户/etc/php-fpm.d/www.conf新增用户:www(userad......
  • [THUPC 2024 初赛] 三步棋
    鸣谢cinccout。赛时两次看出了我的错误/bx。闲话:在我看过的所有人的做题过程中,大家都不约而同的把棋子数量相同时答案相同当作了第一发(。但是很可惜,这个结论是错误的。样例已经给出了当棋子数量为\(2\)的答案,在此我们略去讨论。对于棋子数量为\(1\)答案也很明显是后手......
  • 使用Amber计算单点能三步走
    技术背景Amber是一个在分子动力学中非常常用的一个软件,可以用于进行分子动力学模拟计算,可以与一些软件配合进行增强采样。这里我们简单介绍一下如何使用Amber去计算一个分子构象的单点势能值,及其对应的能量分量。第一步:构造力场文件首先我们需要运行tleap,加载一个力场,例如这里......
  • 电子印章怎么弄?三步教你电子印章在线生成免费教程!
    在这个数字化快速发展的时代,电子印章已经成为日常商务活动中不可或缺的一部分。相对于传统的实体印章,电子印章具有更高的便捷性和安全性,更是无纸化办公中必不可少的一环。那么,电子印章怎么弄呢?跟着下面这三步来操作,就能实现电子印章在线生成免费搞定!第一步:进入微签电子印章注册页面......
  • 三步释放 Vmware 中 Ubuntu 系统占用的空间
    1.清除缓存删除Vmwaretools产生的缓冲文件文件位置:用户目录下.cache/vmware/drag_and_drop,这个路径下的文件都可以删除。为了在windows和ubuntu之间拷贝数据方便,在vmware上安装vmwaretools,之后会在用户目录下的.cache/vmware/drag_and_drop/路径下创建一些缓存区目......
  • Python爬虫必杀技:XPath
    XPath是什么XPath即为XML路径语言,它是一种用来确定XML(标准通用标记语言的子集)文档中某部分位置的语言。XPath基于XML的树状结构,有不同类型的节点,包括元素节点,属性节点和文本节点,提供在数据结构树中找寻节点的能力。跟BeautifulSoup4一样都是用来解析页面内容的工具,只......
  • 接口测试系列文章3——Python接口测试其实只需三步!
    接口测试通用步骤小品中曾说过,大象放冰箱里分三步!分别是:一、把冰箱门打开二、把大象放到冰箱里三、把门关上那么问题来了!通过代码做接口测试分几步呢?答:也分三步!其实无论是手工进行接口测试还是通过代码进行接口测试,三个核心步骤如下:构建接口发送接口校验接口Python编码进行......