2023牛客暑期多校训练营8-C Clamped Sequence II
2023牛客暑期多校训练营8-C Clamped Sequence II
https://ac.nowcoder.com/acm/contest/57362/C
文章目录
- 2023牛客暑期多校训练营8-C Clamped Sequence II
- 题意
- 解题思路
- 代码
题意
解题思路
先考虑不加紧密度的情况,要支持单点修改,整体查询,可以用值域线段树来求。设 t r e e [ x ] . n u m tree[x].num tree[x].num表示数值在 [ l , r ] [l,r] [l,r]区间的数的个数, t r e e [ x ] . s u m tree[x].sum tree[x].sum表示数值在 [ l , r ] [l,r] [l,r]区间的数的总和, t r e e [ x ] . a n s tree[x].ans tree[x].ans表示数值在 [ l , r ] [l,r] [l,r]区间的数的紧密度,结合下图,可以求得转移式:
n u m x = n u m l s o n + n u m r s o n s u m x = n u m l s o n + s u m r s o n a n s x = a n s l s o n + a n s r s o n + s u m r s o n × n u m l s o n − s u m l s o n × n u m r s o n num_x=num_{lson}+num_{rson}\\ sum_x=num_{lson}+sum_{rson}\\ ans_x=ans_{lson}+ans_{rson}+sum_{rson}\times num_{lson}-sum_{lson}\times num_{rson} numx=numlson+numrsonsumx=numlson+sumrsonansx=anslson+ansrson+sumrson×numlson−sumlson×numrson
此时我们加入紧凑的设定,对于每一对确定的 [ l , r ] [l,r] [l,r]我们都可以算出此时的答案:
a n s w e r = a n s l , r + s u m [ l , r ] × ( n u m [ 1 , l − 1 ] − n u m [ r + 1 , n ] ) + ( n u m [ 1 , l − 1 ] + n u m [ l , r ] ) × n u m [ r + 1 , n ] − ( n u m [ r + 1 , n ] + n u m [ l , r ] ) × n u m [ 1 , l − 1 ] answer=ans_{l,r}+sum_{[l,r]}\times(num_{[1,l-1]}-num_{[r+1,n]})+(num_{[1,l-1]}+num_{[l,r]})\\ \times num_{[r+1,n]}-(num_{[r+1,n]}+num_{[l,r]})\times num_{[1,l-1]} answer=ansl,r+sum[l,r]×(num[1,l−1]−num[r+1,n])+(num[1,l−1]+num[l,r])×num[r+1,n]−(num[r+1,n]+num[l,r])×num[1,l−1]
根据出题人所说,该答案是严格单峰的,所以可以用三分求解,但经过我实践却不太像,需要将三分的范围约束在最中间的数 ± d \pm d ±d再加上左右游移 2 ∼ 3 2\sim 3 2∼3个数,大致能求出正确答案。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,M=1e6+5;
ll n,a[N],b[M],q;
struct node{ll num,l,r;ll sum,ans;node operator +(const node a){node t;t.num=num+a.num,t.sum=sum+a.sum;t.ans=num*a.sum-sum*a.num+ans+a.ans;t.l=l,t.r=a.r;return t;}
};
struct tree{node tr[M<<2];void build(int res,int l,int r){tr[res].l=l,tr[res].r=r;if(l==r){tr[res].num=b[l],tr[res].sum=b[l]*l;return;}int mid=l+r>>1;build(res<<1,l,mid);build(res<<1|1,mid+1,r);tr[res]=tr[res<<1]+tr[res<<1|1];}void add(int res,int x,ll d){int l=tr[res].l,r=tr[res].r;if(l==r&&l==x){tr[res].sum+=d*l;tr[res].num+=d;return;}int mid=l+r>>1;if(x<=mid)add(res<<1,x,d);else add(res<<1|1,x,d);tr[res]=tr[res<<1]+tr[res<<1|1];return;}node query(int res,int x,int y){if(x>y)return node{0,0,0,0,0};int l=tr[res].l,r=tr[res].r;if(x<=l&&y>=r){return tr[res];}int mid=l+r>>1;if(y<=mid)return query(res<<1,x,y);if(x>mid)return query(res<<1|1,x,y);return query(res<<1,x,y)+query(res<<1|1,x,y);}int kth(int id,int l,int r,int k){if(l==r) return l;int mid=l+r>>1;if(tr[id<<1].num>=k) return kth(id<<1,l,mid,k);else return kth(id<<1|1,mid+1,r,k-tr[id<<1].num);}
}t;
ll f(int l,int d){int r=l+d;node p=t.query(1,l,r);ll num1=p.num,ans1=p.ans,sum1=p.sum;ll numl=t.query(1,1,l-1).num,numr=t.query(1,r+1,M-1).num;return ans1-numl*(numr+num1)*l+numr*(numl+num1)*r+sum1*(numl-numr);
}
ll work(int d){int k=t.kth(1,1,M-1,n+1>>1);int l=max(1,k-d),r=min(M-1,k+d);ll ma=0;while(l+2<=r){int mi1=(r-l)/3+l,mi2=r-(r-l)/3;ll ma1=f(mi1,d),ma2=f(mi2,d);ma=max(ma,max(ma1,ma2));if(ma1>=ma2)r=mi2-1;else l=mi1+1;}for(int i=l;i<=r;i++)ma=max(ma,f(i,d));return ma;
}
int main(){ios::sync_with_stdio(false);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i],b[a[i]]++;t.build(1,1,M-1);while(q--){int op;cin>>op;if(op==1){int x,d;cin>>x>>d;t.add(1,a[x],-1);t.add(1,d,1);a[x]=d;}else{int d;cin>>d;cout<<work(d)<<'\n';}}
}
相关文章:

2023牛客暑期多校训练营8-C Clamped Sequence II
2023牛客暑期多校训练营8-C Clamped Sequence II https://ac.nowcoder.com/acm/contest/57362/C 文章目录 2023牛客暑期多校训练营8-C Clamped Sequence II题意解题思路代码 题意 解题思路 先考虑不加紧密度的情况,要支持单点修改,整体查询࿰…...

【GitLab私有仓库】如何在Linux上用Gitlab搭建自己的私有库并配置cpolar内网穿透?
文章目录 前言1. 下载Gitlab2. 安装Gitlab3. 启动Gitlab4. 安装cpolar5. 创建隧道配置访问地址6. 固定GitLab访问地址6.1 保留二级子域名6.2 配置二级子域名 7. 测试访问二级子域名 前言 GitLab 是一个用于仓库管理系统的开源项目,使用Git作为代码管理工具…...

企业计算机服务器遭到了locked勒索病毒攻击如何解决,勒索病毒解密
网络技术的不断发展,也为网络安全埋下了隐患,近期,我们收到很多企业的求助,企业的计算机服务器遭到了locked勒索病毒的攻击,导致企业的财务系统内的所有数据被加密无法读取,严重影响了企业的正常运行。最近…...

Redis哨兵模式搭建
Redis主从复制搭建 Redis虽然拥有非常高的性能,但是在实际的生产环境中,使用单机模式还是会产生不少问题的,比如说容易出现 单机故障,容量瓶颈,以及QPS瓶颈等问题。通常环境下,主从复制、哨兵模式、Redis…...
大语言模型控制生成的过程Trick:自定义LogitsProcessor实践
前言 在大模型的生成过程中,部分原生的大语言模型未经过特殊的对齐训练,往往会“胡说八道”的生成一些敏感词语等用户不想生成的词语,最简单粗暴的方式就是在大模型生成的文本之后,添加敏感词库等规则手段进行敏感词过滤…...

Docker容器:docker的资源控制及docker数据管理
文章目录 一.docker的资源控制1.CPU 资源控制1.1 资源控制工具1.2 cgroups有四大功能1.3 设置CPU使用率上限1.4 进行CPU压力测试1.5 设置50%的比例分配CPU使用时间上限1.6 设置CPU资源占用比(设置多个容器时才有效)1.6.1 两个容器测试cpu1.6.2 设置容器绑…...

从零开始打造家装预约咨询小程序
在如今互联网高度发达的时代,家装行业也逐渐意识到了线上渠道的重要性。为了更好地服务客户,提高用户体验,越来越多的家装公司开始寻找合适的小程序制作平台。本文将向大家介绍如何使用第三方制作平台,如乔拓云网,打造…...
es线上处理命令记录
常用命令 搜索 GET _search {"query": {"match_all": {}} }获取全部模版 GET _index_template GET _index_template/yst_crawler_template获取全部索引 GET /_cat/indices?v 获取当前mapping GET /yst_crawler/_mapping创建一个mapping PUT /yst_c…...
mysql 在nodejs中的简单使用(增删改查)
一 、封装SQL查询请求链接 const mysql require(mysql) //创建开发工具数据库链接池 const pool mysql.createPool({host: 192.168.1.133,user: user_name, password: 123456,database: database_name,port: 3306,connectionLimit: 50 // 限制连接数 });// sql:查…...

1.MySQL数据库的基本操作
数据库操作过程: 1.用户在客户端输入 SQL 2.客户端会把 SQL 通过网络发送给服务器 3.服务器执行这个 SQL,把结果返回给客户端 4.客户端收到结果,显示到界面上 数据库的操作 这里的数据库不是代表一个软件,而是代表一个数据集合。 显示当前的数据库 …...

Zabbix-6.4.4 邮箱告警SMS告警配置
目录 ------------------------- # 邮箱告警 ---------------------------------- 1.安装mailx与postfix软件包 2.修改mailx配置文件 3. 创建文件夹 4. 编写mail-send.sh脚本 5. 将该脚本赋予执行权限 6. 进入web界面进行设置—> Alerts —> Media Types 7. 添…...

网络安全 Day30-运维安全项目-容器架构上
容器架构上 1. 什么是容器2. 容器 vs 虚拟机(化) :star::star:3. Docker极速上手指南1)使用rpm包安装docker2) docker下载镜像加速的配置3) 载入镜像大礼包(老师资料包中有) 4. Docker使用案例1) 案例01::star::star::…...
深入理解设计模式-创建型之单例模式
为什么要使用单例 1、表示全局唯一 如果有些数据在系统中应该且只能保存一份,那就应该设计为单例类。 如:配置类:在系统中,我们只有一个配置文件,当配置文件被加载到内存之后,应该被映射为一个唯一的【配…...
Vue中路由缓存问题及解决方法
一.问题 Vue Router 允许你在你的应用中创建多个视图,并根据路由来动态切换这些视图。默认情况下,当你从一个路由切换到另一个路由时,Vue Router 会销毁前一个路由的组件实例并创建新的组件实例。然而,有时候你可能希望保持一些页…...

Linux与bash(基础内容一)
一、常见的linux命令: 1、文件: (1)常见的文件命令: (2)文件属性: (3)修改文件属性: 查看文件的属性: ls -l 查看文件的属性 ls …...

NVIDIA Omniverse与GPT-4结合生成3D内容
全球各行业对 3D 世界和虚拟环境的需求呈指数级增长。3D 工作流程是工业数字化的核心,开发实时模拟来测试和验证自动驾驶车辆和机器人,操作数字孪生来优化工业制造,并为科学发现铺平新的道路。 如今,3D 设计和世界构建仍然是高度…...

Windows Server --- RDP远程桌面服务器激活和RD授权
RDP远程桌面服务器激活和RD授权 一、激活服务器二、设置RD授权 系统:Window server 2008 R2 服务:远程桌面服务 注:该方法适合该远程桌面服务器没网络状态下(离线),激活服务器。 一、激活服务器 1.打开远…...
关于游戏盾
游戏盾(Game Shield)是一种针对游戏行业特点的网络安全解决方案,主要针对游戏平台面临的各种网络攻击和安全威胁。以下是一些原因,说明为什么游戏平台需要加游戏盾: 1. DDoS攻击:游戏平台通常容易受到分布式…...

回归预测 | MATLAB实现基于SSA-KELM-Adaboost麻雀算法优化核极限学习机结合AdaBoost多输入单输出回归预测
回归预测 | MATLAB实现基于SSA-KELM-Adaboost麻雀算法优化核极限学习机结合AdaBoost多输入单输出回归预测 目录 回归预测 | MATLAB实现基于SSA-KELM-Adaboost麻雀算法优化核极限学习机结合AdaBoost多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本…...

《cpolar内网穿透》外网SSH远程连接linux(CentOS)服务器
本次教程我们来实现如何在外公网环境下,SSH远程连接家里/公司的Linux CentOS服务器,无需公网IP,也不需要设置路由器。 视频教程 [video(video-jrpesBrv-1680147672481)(type-csdn)(url-CSDN直播https://live-file.csdnimg.cn/release/live/…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...