【Codeforces Round #853 (Div. 2)】C. Serval and Toxel‘s Arrays【题解】
题目
Toxel likes arrays. Before traveling to the Paldea region, Serval gave him an array aaa as a gift. This array has nnn pairwise distinct elements.
In order to get more arrays, Toxel performed mmm operations with the initial array. In the iii-th operation, he modified the pi-th element of the (i−1i−1i−1)-th array to viv_{i}vi, resulting in the iii-th array (the initial array a is numbered as 000). During modifications, Toxel guaranteed that the elements of each array are still pairwise distinct after each operation.
Finally, Toxel got m+1m+1m+1 arrays and denoted them as A0=a,A1,…,AmA_{0}=a,A_{1},…,A_{m}A0=a,A1,…,Am. For each pair (i,j)(0≤i<j≤m)(i,j) (0≤i<j≤m)(i,j)(0≤i<j≤m), Toxel defines its value as the number of distinct elements of the concatenation of AiA_{i}Ai and AjA_{j}Aj. Now Toxel wonders, what is the sum of the values of all pairs? Please help him to calculate the answer.
It is guaranteed that the sum of nnn and the sum of mmm over all test cases do not exceed 2⋅1052⋅10^{5}2⋅105.
思路
①初始化所有在原始数组中的数的数量为m+1m+1m+1。因为一共有m+1m+1m+1个数组,那么我一开始假定所有数组都与原始数组保持相同。
②对于第i(0≤i<m)i(0≤i<m)i(0≤i<m)个数组,也就是给出一个位置的修改,那么这个位置上原来的数对应的数量就要相应地减少m−im-im−i,因为在当前包括后面一共m−im-im−i个数组中这个位置上的数都要修改,并将其变成vvv,然后vvv的数量相应地增加m−im-im−i。这样,我们就统计出了这m+1m+1m+1个数组中所有不同的数分别出现的次数。
③现在统计这m+1m+1m+1个数组中不同的数分别对答案产生的贡献之和。设某个数的数量是cntcntcnt,那么含有这个数的cntcntcnt个数组与其它m+1−cntm+1-cntm+1−cnt个数组组合时这个数产生的贡献是cnt∗(m+1−cnt)cnt*(m+1-cnt)cnt∗(m+1−cnt);此外,含有这个数的cntcntcnt个数组两两组合时产生的Ccnt2=cnt∗(cnt−1)/2C^{2}_{cnt}=cnt*(cnt-1)/2Ccnt2=cnt∗(cnt−1)/2个组合分别产生了111的贡献。因此,答案就是:
ans=∑1n+m(cnt[i]∗(m+1−cnt[i])+cnt[i]∗(cnt[i]−1)/2)ans = \sum^{n+m}_{1}(cnt[i]*(m+1-cnt[i])+cnt[i]*(cnt[i]-1)/2)ans=∑1n+m(cnt[i]∗(m+1−cnt[i])+cnt[i]∗(cnt[i]−1)/2)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5+5;
ll n,m,a[maxn],cnt[maxn<<1];
void solve(){cin>>n>>m;memset(cnt,0,sizeof(cnt));for(ll i=1;i<=n;i++)cin>>a[i], cnt[a[i]] = m+1;for(ll i=0;i<m;i++){ll p,v;cin>>p>>v;cnt[a[p]] -= (m-i);a[p] = v;cnt[v] += (m-i);}ll ans = 0;for(ll i=1;i<=n+m;i++){if(cnt[i]==0)continue;ans += cnt[i]*(m+1-cnt[i]);ans += cnt[i]*(cnt[i]-1)/2;}cout<<ans<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll tests;cin>>tests;while(tests--){solve();}return 0;
}
相关文章:
【Codeforces Round #853 (Div. 2)】C. Serval and Toxel‘s Arrays【题解】
题目 Toxel likes arrays. Before traveling to the Paldea region, Serval gave him an array aaa as a gift. This array has nnn pairwise distinct elements. In order to get more arrays, Toxel performed mmm operations with the initial array. In the iii-th opera…...

100天精通Python(数据可视化篇)——第77天:数据可视化入门基础大全(万字总结+含常用图表动图展示)
文章目录1. 什么是数据可视化?2. 为什么会用数据可视化?3. 数据可视化的好处?4. 如何使用数据可视化?5. Python数据可视化常用工具1)Matplotlib绘图2)Seaborn绘图3)Bokeh绘图6. 常用图表介绍及其…...
PMP考前冲刺2.27 | 2023新征程,一举拿证
题目1-2:1.在产品开发过程中,项目发起人向项目团队推荐了一种新材料,新材料比现有的材料更便宜而且性能更好。如果团队采用新材料,不但有利于提升产品质量,而且可以显著降低成本。项目经理应该怎么办?A.采用新材料&am…...

【C++】map和set的封装(红黑树)
map和set的封装一、介绍二、stl源码剖析三、仿函数获取数值四、红黑树的迭代器五、map的[]5.1 普通迭代器转const迭代器六、set源码七、map源码八、红黑树源码一、介绍 首先要知道map和set的底层都是用红黑树实现的 【数据结构】红黑树 set只需要一个key,但是map既…...
【批处理脚本】-1.14-移动文件(夹)命令move
"><--点击返回「批处理BAT从入门到精通」总目录--> 共10页精讲(列举了所有move的用法,图文并茂,通俗易懂) 在从事“嵌入式软件开发”和“Autosar工具开发软件”过程中,经常会在其集成开发环境IDE(CodeWarrior,S32K DS,Davinci,EB Tresos,ETAS…)中,…...

逻辑地址和物理地址转换
在操作系统的学习中,很多抵挡都会涉及虚拟地址转换为物理地址的计算,本篇就简单介绍一下在分页存储管理、分段存储管理、磁盘存储管理中涉及的地址转换问题。 虚拟地址与物理地址 编程一般只有可能和逻辑地址打交道,比如在 C 语言中&#x…...

HyperGBM用4记组合拳提升AutoML模型泛化能力
本文作者:杨健,九章云极 DataCanvas 主任架构师 如何有效提高模型的泛化能力,始终是机器学习领域的重要课题。经过大量的实践证明比较有效的方式包括: 利用Early Stopping防止过拟合通过正则化降低模型的复杂度使用更多的训练数…...

P6软件中的前锋线设置
卷首语 所谓前锋线,是指从评估时刻的时标点出发,用点划线一次连接各项活动的实际进展位置所形成的的线段,其通常为折线。 关键路径法 前锋线比较法,是通过在进度计划中绘制实际进度前锋线以判断活动实际进度与计划进度的偏差&a…...

Spring Boot + Vue3 前后端分离 实战 wiki 知识库系统<二>---后端架构完善与接口开发
数据库准备: 在上一次Spring Boot Vue3 前后端分离 实战 wiki 知识库系统<一>---Spring Boot项目搭建已经将SpringBoot相关的配置环境给搭建好了,接下来则需要为咱们的项目创建一个数据库。 1、mysql的安装: 关于mysql的安装这里就…...

如何在logback.xml中自定义动态属性
原文地址:http://blog.jboost.cn/trick-logback-prop.html 当使用logback来记录Web应用的日志时,我们通过在logback.xml中配置appender来指定日志输出格式及输出文件路径,这在一台主机或一个文件系统上部署单个实例没有问题,但是…...

嵌入式系统硬件设计与实践(第一步下载eda软件)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 现实生活中,我们经常发现有的人定了很多的目标,但是到最后一个都没有实现。这听上去有点奇怪,但确实是实实在在…...

Portraiture4免费磨皮插件支持PS/LR
Portraiture 4免去了繁琐的手工劳动,选择性的屏蔽和由像素的平滑,以帮助您实现卓越的肖像润色。智能平滑,并删除不完善之处,同时保持皮肤的纹理和其他重要肖像的细节,如头发,眉毛,睫毛等。 一键…...

Python学习笔记202302
1、numpy.empty 作用:根据给定的维度和数值类型返回一个新的数组,其元素不进行初始化。 用法:numpy.empty(shape, dtypefloat, order‘C’) 2、logging.debug 作用:Python 的日志记录工具,这个模块为应用与库实现了灵…...
2023年大数据面试开胃菜
1、kafka的message包括哪些信息一个Kafka的Message由一个固定长度的header和一个变长的消息体body组成,header部分由一个字节的magic(文件格式)和四个字节的CRC32(用于判断body消息体是否正常)构成。当magic的值为1的时候,会在magic和crc32之间多一个字节…...
优雅的controller层设计
controller层设计 Controller 层逻辑 MVC架构下,我们的web工程结构会分为三层,自下而上是dao层,service层和controller层。controller层为控制层,主要处理外部请求。调用service层,一般情况下,contro…...
同步、通信、死锁
基础概念竞争资源引起两个问题死锁:因资源竞争陷入永远等待的状态饥饿:一个可运行程序由于其他进程总是优先于它,而被调用程序总是无限期地拖延而不能执行进程互斥:若干进程因相互争夺独占型资源而产生的竞争关系进程同步…...

【聚类】谱聚类解读、代码示例
【聚类】谱聚类详解、代码示例 文章目录【聚类】谱聚类详解、代码示例1. 介绍2. 方法解读2.1 先验知识2.1.1 无向权重图2.1.2 拉普拉斯矩阵2.2 构建图(第一步)2.2.1 ϵ\epsilonϵ 邻近法2.2.2 k 近邻法2.2.3 全连接法2.3 切图(第二步…...
最牛逼的垃圾回收期ZGC(1),简介
1丶什么是ZGC? ZGC是JDK 11中引入的一种可扩展的、低延迟的垃圾收集器。ZGC最主要的特点是:在非常短的时间内(一般不到10ms),就可以完成一次垃圾回收,而且这个时间是与堆的大小无关的。另外,ZGC支持非常大…...

微服务的Feign到底是什么
Feign是什么 分区是一种数据库优化技术,它可以将大表按照一定的规则分成多个小表,从而提高查询和维护的效率。在分区的过程中,数据库会将数据按照分区规则分配到不同的分区中,并且可以在分区中使用索引和其他优化技术来提高查询效…...

JavaScript 正则表达式
正则表达式(英语:Regular Expression,在代码中常简写为regex、regexp或RE)使用单个字符串来描述、匹配一系列符合某个句法规则的字符串搜索模式。搜索模式可用于文本搜索和文本替换。什么是正则表达式?正则表达式是由一…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...

6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...