当前位置: 首页 > news >正文

赛后补题:CF1789C Serval and Toxel‘s Arrays

传送门:CF

题目描述:

题目较长,此处省略
输入:
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
输出:
13
1
705

比赛的时候感觉已经想到了正解,但是没有想的很清楚,所以赛时没有打出来.

我认为这道题的突破口其实是在ai<=n+ma_i<=n+mai<=n+m这里的.有了这个,所以我们最终的算法能够不是n2n^2n2,但是赛时我甚至没有注意到这一点(笑

对于每一个数组中的一个数字来说,我们考虑计算这个数字在其他所有数组中的贡献.我们会发现当这个数字不在其他数组中的时候,显然我们可以得到一个贡献,但是当我们的这个数字在其他数组中的时候,我们此时的这个数字在这个数组中是没有贡献的.我们可以先假装这个数字在其他数组中是没有的,那么此时我们的总贡献就是m∗(1+m)/2m*(1+m)/2m(1+m)/2(一共有m+1个数组).但是我们此时可能有一种情况就是有重复数字的贡献,所以我们考虑将这个重复数字的贡献减掉.我们可以计算出在所有m+1m+1m+1个数组中这个数字的个数cntcntcnt,那么对于所有的数组来说,我们之前所重复计算的就是cnt∗(cnt−1)cnt*(cnt-1)cnt(cnt1)[也就是这cnt个数组两两配对的个数],那么此时我们的这个数字的总贡献就是m∗(m+1)/2−cnt∗(cnt−1)m*(m+1)/2-cnt*(cnt-1)m(m+1)/2cnt(cnt1)

所以我们此时的问题就变成了如何计算出这么多的数组里面每一个数字的个数.每一次更改时,我们可以使用lastlastlast数组来记录上一次该数字出现的位置,然后计算一下这个数字知道消失所存在的数组此处即可.并且需要注意的我们还需要累计每一个数字一直到最后的存在的次数

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;int n;int m;int last[maxn];
int a[maxn];int cnt[maxn];
void init() {for(int i=1;i<=n+m;i++) {last[i]=-1;cnt[i]=0;}
}
signed main() {T=read();while(T--) {n=read();m=read();init();for(int i=1;i<=n;i++){a[i]=read();last[a[i]]=0;} for(int i=1;i<=m;i++) {int pos=read(),val=read();cnt[a[pos]]+=i-last[a[pos]];last[a[pos]]=-1;last[val]=i;a[pos]=val;}for(int i=1;i<=n+m;i++) {if(last[i]!=-1) {cnt[i]+=(m+1-last[i]);}}ll ans=2*n*(m+1)*(m)/2;for(int i=1;i<=n+m;i++) {ans-=cnt[i]*(cnt[i]-1)/2;}printf("%lld\n",ans);}return 0;
}

相关文章:

赛后补题:CF1789C Serval and Toxel‘s Arrays

传送门:CF 题目描述: 题目较长,此处省略 输入: 3 3 2 1 2 3 1 4 2 5 1 1 1 1 1 10 10 4 6 9 12 16 20 2 10 19 7 1 3 5 4 2 17 2 18 6 11 7 1 8 17 5 5 5 5 2 2 输出: 13 1 705比赛的时候感觉已经想到了正解,但是没有想的很清楚,所以赛时没有打出来. 我认为这道题的突破口其…...

Linux学习(8.7)命令与文件的搜寻

目录 命令与文件的搜寻 which 文件档名的搜寻&#xff1a; whereis (寻找特定文件) locate find 以下内容转载自鸟哥的Linux私房菜 命令与文件的搜寻 which 这个命令是根据『PATH』这个环境变量所规范的路径&#xff0c;去搜寻『运行档』的档名&#xff5e; 所以&am…...

Linux下 Makefile文件基本语法二

本文继续上一篇关于 Makefile 文件内容的介绍。上一篇文章如下&#xff1a; Linux下 Makefile 基本语法_凌雪舞的博客-CSDN博客 一. Makefile 上一篇文章介绍了 Makefile基本语法中的变量&#xff0c;模式规则&#xff0c;自动化变量。这里继续介绍 Makefile 的另外一些语…...

【前端】JavaScript构造函数

文章目录概念执行过程返回值原型与constructor继承方式原型链其他继承方式&#xff08;还没写&#xff09;参考概念 在JS中&#xff0c;通过new来实例化对象的函数叫构造函数。实例化对象&#xff0c;也就是初始化一个实例对象。构造函数一般首字母大写。 构造函数的目的&…...

STM32单片机之温湿度检测系统(DTH11、OLED、LCD1602)

LCD1602LCD1602引脚第 1 脚: VSS 为电源地 第 2 脚: VDD 接 5V 正电源 第 3 脚: VL 为液晶显示器对比度调整端,接正电源时对比度最弱&#xff0c;接地时对比度最高&#xff0c;对比度过高时会产生“鬼影”&#xff0c;使用时可以通过一个 10K 的电位器调整对比度。 第 4 脚&…...

vitepress 就这几步操作,博客就搭好啦?

Ⅰ、什么是vitepress &#x1f48e; vitepress 使用场景 简单的说 &#xff0c;只要 会用 markdown 语法&#xff0c;就能构建自己的 「博客、笔记、使用文档」等系统 &#xff1b; ✨ vitepress 优势 优势介绍傻瓜式操作只需要配置 菜单 和 对应的 markdown 就能实现博客、笔…...

【Python工具篇】Anaconda中安装python2和python3以及在pycharm中使用

背景&#xff1a;已经安装好anaconda、python3、pycharm&#xff0c;因为项目使用的是python2语法&#xff0c;所以需要在anaconda中安装python2&#xff0c;并在pycharm中使用&#xff0c;下面给出步骤。 1. 打开cmd或者是Anaconda Prompt。 下面是anaconda prompt. 2. 查…...

Android 网络框架——Retrofit源码精析

众所周知&#xff0c;Retrofit是OkHttp的封装&#xff0c;APP对网络交互部分的实现基本上都是RxJavaRetrofitOkHttp架构&#xff08;或协程RetrofitOkHttp&#xff09;&#xff0c;可以说&#xff0c;Retrofit已经广为人知。本文主要介绍Retrofit主线源码实现机制&#xff0c;及…...

分布式算法 - Snowflake算法

Snowflake&#xff0c;雪花算法是由Twitter开源的分布式ID生成算法&#xff0c;以划分命名空间的方式将 64-bit位分割成多个部分&#xff0c;每个部分代表不同的含义。这种就是将64位划分为不同的段&#xff0c;每段代表不同的涵义&#xff0c;基本就是时间戳、机器ID和序列数。…...

【java web篇】Maven的基本使用以及IDEA 配置Maven

&#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是阿牛&#xff0c;全栈领域优质创作者。&#x1f61c;&#x1f4dd; 个人主页&#xff1a;馆主阿牛&#x1f525;&#x1f389; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4d…...

【蓝桥集训】第七天并查集

作者&#xff1a;指针不指南吗 专栏&#xff1a;Acwing 蓝桥集训每日一题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录1.亲戚2.合并集合3.连通块中点的数量有关并查集的知识学习可以移步至—— 【算法】——并查集1.亲戚 或许你并不知道&#…...

【Playwright】扑面而来的Playwright测试框架

在当今快节奏的开发环境中&#xff0c;测试是软件开发的重要组成部分。 Microsoft Playwright 是一种流行的测试自动化框架&#xff0c;允许开发人员为 Web 应用程序编写端到端测试。 Playwright 建立在 Puppeteer 之上&#xff0c;这是另一个流行的测试自动化框架。在这篇博文…...

React(三) ——新、旧生命周期

&#x1f9c1;个人主页&#xff1a;个人主页 ✌支持我 &#xff1a;点赞&#x1f44d;收藏&#x1f33c;关注&#x1f9e1; 文章目录⛳React生命周期&#x1f30b;初始化阶段&#x1f463;运行中阶段&#x1f3d3;销毁阶段&#x1f3eb;新生命周期的替代&#x1f69a;react中性…...

IT男的一次中年破局尝试--出书

一、转战外企 接上回《人到中年——IT男择业感悟》后&#xff0c;自己从大央企去了某知名外企。外企虽然最近几年的日子已经没有10年前的辉煌与滋润&#xff0c;但相对来说&#xff0c;还能勉强找到工作与生活的平衡点。 划重点&#xff0c;35岁上下的人换工作理由&#xf…...

Python 内置函数eval()

Python 内置函数eval() eval(expression, globalsNone, localsNone) 函数用来执行一个字符串表达式&#xff0c;并返回表达式的值。 expression: 字符串表达式。global: 可选&#xff0c;globals必须是一个字典。locals: 可选&#xff0c;locals可以是任何映射对象。 示例 &…...

【ArcGIS Pro二次开发】系列学习笔记,持续更新,记得收藏

一、前言 这个系列是本人的一个学习笔记。 作为一个ArcGIS Pro二次开发的初学者&#xff0c;最困扰的就是无从入手。网上关于ArcGIS Pro二次开发的中文资料极少&#xff0c;官方文档对于我这样的英文苦手又太不友好。 在搜索无果后&#xff0c;决定自已动手&#xff0c;从头…...

EasyRecovery16MAC苹果版本Photo最新版数据恢复软件

无论是在工作学习中&#xff0c;还是在生活中&#xff0c;Word、Excle等办公软件都是大家很常用的。我们在使用电脑的过程中&#xff0c;有时会因自己的误删或电脑故障&#xff0c;从而导致我们所写的文档丢失了。出现这样的大家不要着急&#xff0c;今天小编就给大家推荐一款可…...

Go的string与strings.Builder

Go的string与strings.Builder 文章目录Go的string与strings.Builder一、strings.Builder 的优势二、string类型的值三、与string相比&#xff0c;Builder的优势体现在拼接方面3.1 Builder的拼接&#xff0c;与Builder的自动扩容3.2 手动扩容3.3 Builder 的重用四、strings.Buil…...

8.Spring Security 权限控制

1.简介入门JavaEE和SpringMVC &#xff1a;Spring Security就是通过11个Fliter进行组合管理小Demouser实体类user.type字段&#xff0c;0普通用户&#xff0c;1超级管理员&#xff0c;2版主补全get set tostringimplement UserDetails&#xff0c;重写以下方法// true: 账号未过…...

curl / python+selenium爬取网页信息

Python爬取网页信息 需求: 持续爬取某嵌入式设备配置网页上的状态信息 shell脚本 简单快速, 不用装插件只能爬取静态内容 用curl命令返回整个网页的内容用grep命令抓取其中某些字段结合正则表达式可多样查找但对于动态内容, 比如对某嵌入式设备配置网页上的一条不断更新的信…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...