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

压制二元组的总价值

压制二元组的总价值

对于每一个 a i a_i ai, 看它能压制它前面的多少个元素, 那么它对总价值的贡献就是:

在a数组中:

  1. a i a_i ai压制了x个数, 贡献为: x ∗ i x*i xi
  2. a i a_i ai所压制的所有数在 a a a中的下标和为 y y y, 贡献为 − y -y y

树状数组来求:

  1. 为了快速求出 a i a_i ai压制了几个数, 记录 a i a_i ai前面的所有数在 b b b中的下标 m a p ( a [ i ] ) map(a[i]) map(a[i]),值 t r b [ m a p ( a [ i ] ) ] = 1 trb[map(a[i])]=1 trb[map(a[i])]=1表示它出现过,

​ 这样每次只需通过 s u m ( m a p [ a [ i ] ] ) sum(map[a[i]]) sum(map[a[i]])即可得出它前面已经出现了多少个数.

  1. 记录 a i a_i ai前面的所有数在b中的下标 m a p ( a [ i ] ) map(a[i]) map(a[i]), 值 t r a [ m a p ( a [ i ] ) ] tra[map(a[i])] tra[map(a[i])]为它在 a a a中的下标 i i i, 每次 s u m sum sum即可得出它所压制的所有数的下标和.
import java.io.*;
import java.util.*;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer stmInput = new StreamTokenizer(br);static int N = 200010;static long tra[] = new long[N], trb[] = new long[N];static int a[] = new int[N], b[] = new int[N];static HashMap<Integer, Integer> map = new HashMap<>();static int n;public static int readInt() throws IOException {stmInput.nextToken();return (int) stmInput.nval;}public static int lowbit(int x){return x & -x;}public static void add(int x, int c, long tr[]){for (int i = x; i <= n; i += lowbit(i)) {tr[i] += c;}}public static long sum(int x, long tr[]){long res = 0;for (int i = x; i >= 1; i -= lowbit(i)) {res += tr[i];}return res;}public static void solve() throws IOException{n = readInt();for (int i = 1; i <= n; i++) {a[i] = readInt();}for (int i = 1; i <= n; i++) {b[i] = readInt();map.put(b[i], i);}long ans = 0;for (int i = 1; i <= n; i++) {// 1.ai压制了多少个数ans += i * sum(map.get(a[i]), tra);add(map.get(a[i]), 1, tra);// 2.被ai压制的所有数在a中的下标和ans -= sum(map.get(a[i]), trb);add(map.get(a[i]), i, trb);}pw.println(ans);}public static void main(String[] args) throws IOException {int T = 1;while(T-- != 0){solve();}pw.flush();pw.close();br.close();}}

相关文章:

压制二元组的总价值

压制二元组的总价值 对于每一个 a i a_i ai​, 看它能压制它前面的多少个元素, 那么它对总价值的贡献就是: 在a数组中: a i a_i ai​压制了x个数, 贡献为: x ∗ i x*i x∗i被 a i a_i ai​所压制的所有数在 a a a中的下标和为 y y y, 贡献为 − y -y −y 树状数组来求: 为了…...

【习题】保存应用数据

判断题 1. 首选项是关系型数据库。 错误(False) 2. 应用中涉及到Student信息&#xff0c;如包含姓名&#xff0c;性别&#xff0c;年龄&#xff0c;身高等信息可以用首选项来存储。 错误(False) 3. 同一应用或进程中每个文件仅存在一个Preferences实例。 正确(True) 单选题 …...

Flask框架小程序后端分离开发学习笔记《5》简易服务器代码

Flask框架小程序后端分离开发学习笔记《5》 Flask是使用python的后端&#xff0c;由于小程序需要后端开发&#xff0c;遂学习一下后端开发。 简易服务器代码 接口解析那一块很关键&#xff0c;学后端服务器这一块&#xff0c;感觉主要就是学习相应地址的接口怎么处理。 然后…...

“计算机视觉处理设计开发工程师”专项培训(第二期)

“人工智能技术与咨询” 发布...

R语言学习case7:ggplot基础画图(核密度图)

step1: 导入ggplot2库文件 library(ggplot2)step2&#xff1a;带入自带的iris数据集 iris <- datasets::irisstep3&#xff1a;查看数据信息 dim(iris)维度为 [150,5] head(iris)查看数据前6行的信息 step4&#xff1a;画图展示 plot2 <- ggplot(iris,aes(Sepal.W…...

Ubuntu18配置Docker

1.基本过程 1.更新软件源列表 sudo apt update2.安装软件包依赖 sudo apt install apt-transport-https ca-certificates curl software-properties-common3.在系统中添加Docker的官方密钥 curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add - …...

Keil/MDK平台 - 结构体成员指针注意事项

文章目录 1 . 前言总结2 . 问题现象3 . 解决思路4 . 细节扩展5 . 总结 【极客技术传送门】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 1 . 前言总结 有时候希望通过类定义的类型指向数据包来解析&#xff0c;恰好又想结构体内定义指针指向一段数据&…...

一款超级好用的远程控制APP,你值得拥有

在这个科技日新月异的时代&#xff0c;我们的生活被各种手机软件所包围。几乎每个人都有一个甚至多个手机&#xff0c;你是否也有遇到过需要远程操作自己某一台手机的场景呢&#xff1f;今天&#xff0c;我要向大家推荐一款神奇的手机远程操作神器&#xff0c;让你可以随时随地…...

NumPy必知必会50例 | 18. 使用 NumPy 解决线性方程组:数学问题的实用解决方案

继续我们的 NumPy 探索之旅吧&#xff0c;接下来我们将探讨使用 NumPy 解决线性方程组&#xff0c;一种实用的数学应用。 文章目录 18. 使用 NumPy 解决线性方程组&#xff1a;数学问题的实用解决方案线性方程组&#xff1a;数学世界的基石创建线性方程组 解决实际问题应用场景…...

C/C++编码问题研究

文章目录 一、Unicode字符集与U8/U16/U32编码二、编码1. 占字节数2. ASCII、GB2312、GBK、GB18030 以及 UTF8 的关系3. BOM4. UTF-8的存储实现 三、编译器字符集设置1. GCC语法Example 2. MSVC语法Example 三、wchar_t五、编码转换函数六、代码 & 实践1. UTF8与UTF16、UTF3…...

二刷代码随想录|Java版|回溯算法3|子集问题

习题 2.3 子集问题 就是组合过程收集path。就像是代码随想录里说得那样&#xff0c;组合和分割问题就是收集叶子结点&#xff0c;子集问题就是收集每一个节点。 有涉及到同层重复元素的问题。 先排序&#xff0c;后再for循环里处理相同数值跳过。 设置函数内的used。 还可以用…...

mongodb config

windows&#xff1a; 1.同级bin&#xff0c;data&#xff0c;log创建mongo.config文件 dbpathD:\Program\mongodb\data\db logpathD:\Program\mongodb\log\mongo.log logappendtrue #默认启用日志 journaltrue #过滤无用日志信息&#xff0c;调试设置为false quiettrue port2…...

pytorch 实现中文文本分类

&#x1f368; 本文为[&#x1f517;365天深度学习训练营学习记录博客&#x1f366; 参考文章&#xff1a;365天深度学习训练营&#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制]\n&#x1f680; 文章来源&#xff1a;[K同学的学习圈子](https://www.yuque.com/mi…...

【MySQL】聚合函数和内置函数

文章目录 1 :peach:聚合函数:peach:2 :peach:group by子句的使用:peach:3 :peach:内置函数:peach:3.1 :apple:日期函数:apple:3.2 :apple:字符串函数:apple:3.3 :apple:数学函数:apple: 4 :peach:其它函数:peach: 1 &#x1f351;聚合函数&#x1f351; 函数说明COUNT([DISTIN…...

python第五节:集合set(4)

集合其他方法&#xff1a; len(s) set 的长度 x in s x 是否是 s 的成员 x not in s x 是否不是 s 的成员 s.issubset(t) 是否 s 中的每一个元素都在 t 中 s.issuperset(t) 是否 t 中的每一个元素都在 s s.union(t) 返回一个新的 set 包含 s 和 t 中的每一个元素 …...

知识笔记(一百)———什么是okhttp?

OkHttp简介&#xff1a; OkHttp 是一个开源的、高效的 HTTP 客户端库&#xff0c;由 Square 公司开发和维护。它为 Android 和 Java 应用程序提供了简单、强大、灵活的 HTTP 请求和响应的处理方式。OkHttp 的设计目标是使网络请求变得更加简单、快速、高效&#xff0c;并且支持…...

Electron桌面应用实战:Element UI 导航栏橙色轮廓之谜与Bootstrap样式冲突解决方案

目录 引言 问题现象及排查过程 描述问题 深入探索 查明原因 解决方案与策略探讨 重写样式 禁用 Bootstrap 样式片段 深度定制 Element UI 组件 隔离样式作用域 结语 引言 在基于 Electron 开发桌面应用的过程中&#xff0c;我们可能时常遇到各种意想不到的问题…...

Nuget包缓存存放位置迁移

一、背景 默认情况下&#xff0c;NuGet会将项目中使用的包缓存到C盘&#xff0c;随着项目开发积累nuget包越来越多&#xff0c;这会逐渐挤占大量C盘空间&#xff0c;所以我们可以将nuget包缓存位置指定到其他盘中存放。 二、软件环境 win10、vs2022 三、查看当前缓存存放位…...

键盘上Ins键的作用

前几天编写文档时&#xff0c;发现一个问题&#xff1a;插入内容时&#xff0c;输入的字符将会覆盖光标位置后的字符。原来是按到了键盘上的 Ins键&#xff0c;解决方法是&#xff1a;再按一次 Ins键&#xff08;Ins键如果独立作为一键时&#xff0c;否则使用 “Fn Ins”组合键…...

css display 左右对齐 技巧

.list_number{ display: flex; } .list_name_number{ width:100px; } //左边固定width .list_name_type{ //右边给flex:2 自动撑开 flex:2; }...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...

SFTrack:面向警务无人机的自适应多目标跟踪算法——突破小尺度高速运动目标的追踪瓶颈

【导读】 本文针对无人机&#xff08;UAV&#xff09;视频中目标尺寸小、运动快导致的多目标跟踪难题&#xff0c;提出一种更简单高效的方法。核心创新在于从低置信度检测启动跟踪&#xff08;贴合无人机场景特性&#xff09;&#xff0c;并改进传统外观匹配算法以关联此类检测…...

循环神经网络(RNN):从理论到翻译

循环神经网络&#xff08;RNN&#xff09;是一种专为处理序列数据设计的神经网络&#xff0c;如时间序列、自然语言或语音。与传统的全连接神经网络不同&#xff0c;RNN具有"记忆"功能&#xff0c;通过循环传递信息&#xff0c;使其特别适合需要考虑上下文或顺序的任…...