【DS】河南省第十三届ICPC大学生程序设计竞赛 J-甜甜圈

明天就要省赛了,感觉已经寄了捏

J-甜甜圈_河南省第十三届ICPC大学生程序设计竞赛(重现赛) (nowcoder.com)

题意:

思路:

直接模拟复杂度太高,因此考虑用DS优化

我们考虑用树状数组维护

在用线段树和树状数组之前,先去考虑好我们要维护的是哪个序列,我们需要维护的是序列的什么值

对于这道题,首先需要构造序列

因为他有两根,因此考虑把两根棒合并成一根,然后维护这一根就行

那就是把这两根棒头对头放着就行

每次操作我们找出最大值的位置,贡献加上该最大值头上有几个,然后把它删除

删除其实就是把1变成0

至于怎么去维护贡献,只需要记录上一次删除的位置即可

对于第一次删除,上一次删除的位置在n

这样就可以直接维护了,这题用线段树和也可以做!

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define low(x) ((x)&(-x))
const int mxn=1e5+10;
const int mxe=1e5+10;
struct ty{
	int x,y;
	bool operator<(const ty&a)const{
		return a.y<y;
	}
}a[mxn];
int n,m;
int bitree[mxe<<2];
void init(){
	for(int i=0;i<=n+m;i++) bitree[i]=0;
}
int sum(int x){
	int res=0;
    for(int i=x;i;i-=low(i)) res+=bitree[i];
    return res;
}
void insert(int pos,int x){
	for(int i=pos;i<=n+m;i+=low(i)) bitree[i]+=x;
}
void solve(){
	cin>>n>>m;
	for(int i=n;i>=1;i--){
		insert(i,1);
		cin>>a[i].y;
		a[i].x=i;
	}
	for(int i=n+1;i<=n+m;i++){
		insert(i,1);
		cin>>a[i].y;
		a[i].x=i;
	}
	a[0].x=n;
	sort(a+1,a+1+n+m);
	int ans=0;
	for(int i=1;i<=n+m;i++){
		insert(a[i].x,-1);
		//cout<<sum(a[i].x)<<'\n';
		ans+=abs(sum(a[i].x)-sum(a[i-1].x));
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int __=1;//cin>>__;
	while(__--)solve();return 0;
}#include <bits/stdc++.h>
using namespace std;
#define int long long
#define low(x) ((x)&(-x))
const int mxn=1e5+10;
const int mxe=1e5+10;
struct ty{
	int x,y;
	bool operator<(const ty&a)const{
		return a.y<y;
	}
}a[mxn];
int n,m;
int bitree[mxe<<2];
void init(){
	for(int i=0;i<=n+m;i++) bitree[i]=0;
}
int sum(int x){
	int res=0;
    for(int i=x;i;i-=low(i)) res+=bitree[i];
    return res;
}
void insert(int pos,int x){
	for(int i=pos;i<=n+m;i+=low(i)) bitree[i]+=x;
}
void solve(){
	cin>>n>>m;
	for(int i=n;i>=1;i--){
		insert(i,1);
		cin>>a[i].y;
		a[i].x=i;
	}
	for(int i=n+1;i<=n+m;i++){
		insert(i,1);
		cin>>a[i].y;
		a[i].x=i;
	}
	a[0].x=n;
	sort(a+1,a+1+n+m);
	int ans=0;
	for(int i=1;i<=n+m;i++){
		insert(a[i].x,-1);
		//cout<<sum(a[i].x)<<'\n';
		ans+=abs(sum(a[i].x)-sum(a[i-1].x));
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int __=1;//cin>>__;
	while(__--)solve();return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/9920.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MYSQL Row 752 was cut by GROUP_CONCAT()

因为group_concat有个最大长度的限制&#xff0c;GROUP_CONCAT函数返回的结果大小被MySQL默认限制为1024(字节)的长度。超过最大长度就会被截断掉 解决方法&#xff1a;更改配置文件&#xff0c;修改长度。 https://blog.csdn.net/zzddada/article/details/115082236 concat…

网络的基本概念

作者&#xff1a;爱塔居 专栏&#xff1a;JavaEE 作者简介&#xff1a;大三学生&#xff0c;希望和大家一起进步 文章简介&#xff1a;主要概述IP地址、端口号、协议、协议分层、封装、分用、客户端、服务器、请求、响应、两台主机之间的网络通信流程。 文章目录 目录 文章目录…

Yolo V7详解及openvino部署

论文: https://arxiv.org/abs/2207.02696 代码: https://github.com/WongKinYiu/yolov7 Anchor Anchor是一种用于目标检测的先验框(prior box)生成方法&#xff0c;由Ren等人在2015年提出。Anchor可以在不同尺度和不同纵横比下生成多个先验框&#xff0c;并通过与真实目标框的…

java equals和==的区别

目录一、equals1.前言2.重写equals方法二、三、equals和的区别一、equals 1.前言 **当用equals来比较两个引用数据类型时默认比较的是它们的地址值&#xff0c;比如创建两个成员变量完全相同对象A和对象B两个进行比较&#xff0c;比较的是两个对象的地址值是否相等&#xff0c…

〖Python网络爬虫实战⑫〗- XPATH语法介绍

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;目前专栏免费订阅&#xff0c;在转为付费专栏前订阅本专栏的&#xff0c;可以免费订阅付费…

【三十天精通Vue 3】第二天 Vue 3带来的新特性

✅创作者&#xff1a;陈书予 &#x1f389;个人主页&#xff1a;陈书予的个人主页 &#x1f341;陈书予的个人社区&#xff0c;欢迎你的加入: 陈书予的社区 &#x1f31f;专栏地址: 三十天精通 Vue 3 文章目录引言一、 Vue 3 组件化架构1.1 Composition API1.2 Vuex 3 更新1.3…

OpenGL编程指南-freeglut安装(Windows平台)

OpenGL编程指南-freeglut安装&#xff08;Windows平台&#xff09; 1、前言 学习OpenGL编程首先需要可以跟着书中的示例代码进行学习。书中使用GLUT作为示例代码的演示&#xff0c;GLUT于1998年作者不在维护并不开源&#xff0c;freeglut是一个完美的代替方案。以后我们将会通…

23年5月高项学习笔记12 —— 干系人管理

过程&#xff1a; 1. 识别干系人&#xff1a;定期识别干系人&#xff0c;分析和记录他们的利益&#xff0c;参与度、相互依赖性、影响力和对项目的潜在的影响 输入&#xff1a;立项管理文件、沟通管理计划、干系人参与计划、需求文件、变更日志、问题日志、协议&#xff08;协…

MySQL事物(基础篇)

MySQL事务事物的基本概念事物的ACID属性事务的使用事务隔离级别MVCC&ReadViewMySQL是否还存在幻读事物的基本概念 Transaction作为关系型数据库的核心组成&#xff0c;在数据安全方面有着非常重要的作用&#xff0c;本文会一步步解析事务的核心特性&#xff0c;以获得对事…

STM32CubeMx+HAL库实现USB CDC+MSC复合设备

之前的文章中介绍过STM32的USB应用&#xff0c;包括虚拟串口&#xff08;CDC&#xff09;和大容量存储设备&#xff08;MSC&#xff09;。今天来介绍USB实现CDC和MSC复合设备的方法。 硬件&#xff1a;STM32F407VET6 软件&#xff1a;STM32CubeMx v6.5F4库v1.27.1 编译环境&a…

自动驾驶概述

自动驾驶是指利用计算机视觉、机器学习、传感器等技术&#xff0c;使汽车或其他交通工具能够在没有人类干预的情况下&#xff0c;完成自主导航和行驶任务。自动驾驶技术可以提高交通安全、减少交通拥堵、提高车辆利用率等&#xff0c;并对未来的城市交通和交通工具设计产生深远…

采购招投标系统-高效管控招采流程-降低采购成本

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及…

【SpringBoot技术专题】「实战指南」从实战开发角度去分析操作RestTemplate的应用及使用技巧

前提介绍 当你的应用程序需要访问远程接口时&#xff0c;很容易被不同的浏览器和API调用协议弄晕。幸运的是&#xff0c;Spring框架已为我们提供了一个简单而功能强大的RestTemplate工具&#xff0c;它可以轻松地处理这些基础任务并提供一个简单的方式来访问各种API。 RestTe…

零售数据分析之操作篇12:子查询的应用

各位数据的朋友&#xff0c;大家好&#xff0c;我是老周道数据&#xff0c;和你一起&#xff0c;用常人思维数据分析&#xff0c;通过数据讲故事。 上期内容与作业 上一讲讲了占比相关内存计算的应用场景&#xff0c;包括占比、TOP占比、累计占比等&#xff0c;不同的占比&am…

Explain分析示例

Explain分析示例示例表explain 两个变种explain中的列1. id列2. select_type列3. table列4. type列NULL&#xff1a;const, system&#xff1a;eq_ref&#xff1a;ref&#xff1a;range&#xff1a;index&#xff1a;ALL&#xff1a;5.possible_keys列6. key列7. key_len列8. r…

Matlab simulink上手控制仿真学习笔记3-常用模块S Function及使用案例

讲得真的十分细致&#xff01;个人感觉看完前4节就差不多了。 今天记录的是S Function。 内容比较多&#xff0c;加个目录&#xff1a; S Function前置工作1.1 parameter.m1.2 plant.mfunction [sys,x0,str,ts,simStateCompliance] plant(t,x,u,flag,pa)function [sys,x0,str…

《Kubernetes部署篇:Ubuntu20.04基于containerd二进制部署K8S 1.24.12集群(一主多从)》

一、架构图 如下图所示&#xff1a; 如下图所示&#xff1a; 二、环境信息 1、部署规划 主机名IP地址操作系统内核版本软件说明etcd01192.168.1.62Ubuntu 20.04.5 LTS5.15.0-69-genericetcd02192.168.1.63Ubuntu 20.04.5 LTS5.15.0-69-genericetcd03192.168.1.64Ubuntu 20.04.…

第三章 运算符

文章目录1. 什么是运算符2 算术运算符2.1 基本四则运算符 、-、*、/、%2.2 增量赋值运算符 、- 、* 、/ 、%2.3 自增/自减运算符 、--3. 关系运算符4. 逻辑运算符5. 位运算符6. 移位运算7. 条件运算符8. 运算符的优先级1. 什么是运算符 计算机的最基本的用途之一就是执行数学运…

Web Components 技术分析

简括&#xff1a; Web Components 基于四个主要的规范&#xff1a; Custom Elements&#xff0c;Shadow DOM&#xff0c;HTML Templates 和 HTML Imports。 Custom Elements 可以让开发人员创建自定义的 HTML 标签。 Shadow DOM 可以让开发人员将样式和行为封装到自定义元素内…

C/C++|物联网开发入门+项目实战|C语言基础|玩转c代码---从输入输出开始-学习笔记(6)

文章目录玩转c代码---从输入输出开始参考教程&#xff1a;C语言编程:一本全面的C语言入门教程&#xff08;第3版)第16章需要掌握的内容需要了解的内容常见的人机交互接口串口的输入输出PC常用的几个输入输出函数示例代码3 printf函数使用难点分析A.格式控制字符串的基本形式:示…