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/…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...