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

CF 896 C Willem, Chtholly and Seniorious(珂朵莉树模板)

CF 896 C. Willem, Chtholly and Seniorious(珂朵莉树模板)

Problem - C - Codeforces

大意:给出一个区间 , 要求进行四种操作 , 区间加 , 区间第k大 , 区间推平 , 区间求和。

珂朵莉树模板题 , 练手即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;struct node{int l , r;mutable int v;node(int l , int r = 0 , int v = 0) : l(l), r(r), v(v){}bool operator < (const node &a) const {return l < a.l;}
};set<node>s;set<node>::iterator split(int pos){set<node>::iterator it = s.lower_bound(node(pos));if(it != s.end() && it->l == pos) {return it;}it--;if (it->r < pos) return s.end();int l = it->l;int r = it->r;int v = it->v;s.erase(it);s.insert(node(l , pos - 1 , v));return s.insert(node(pos , r , v)).first;
}inline int qp(int x , int y , int p){int res = 1 % p;x = x % p; while(y){if(y & 1) res = res * x % p;x = x * x % p;y >>= 1;}return res;
}void assign(int l , int r , int x) {set<node>::iterator itr = split(r + 1) , itl = split(l);s.erase(itl , itr);s.insert(node(l , r , x));
}void add(int l , int r , int x){set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++)  i->v += x;
}inline int kth(int l , int r , int x){vector<PII>v;set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++) v.emplace_back(i->v , i->r - i->l + 1);sort(v.begin() , v.end());for(auto [val , num] : v){if(x > num) x -= num;else return val;}
}inline int sum(int l , int r , int x , int p){int res = 0;set<node>::iterator itr = split(r + 1) , itl = split(l);for(auto i = itl ; i != itr ; i ++){res = (res + qp(i->v , x , p) * (i->r - i->l + 1) % p) % p;}return res;
}int n , m , seed , vmax , op , a[N] , x , y , l , r;inline int rnd(){int res = seed;seed = (seed * 7 + 13) % mod;return res;
}signed main(){IOScin >> n >> m >> seed >> vmax;for(int i = 1 ; i <= n ; i ++){a[i] = (rnd() % vmax) + 1;s.insert(node{i , i , a[i]});}for(int i = 1 ; i <= m ; i ++){op = rnd() % 4 + 1;l = rnd() % n + 1;r = rnd() % n + 1;if(l > r) swap(l , r);if(op == 3){x = rnd() % (r - l + 1) + 1;}else{x = rnd() % vmax + 1;}if(op == 4) y = rnd() % vmax + 1;if(op == 1) add(l , r , x);if(op == 2) assign(l , r , x);if(op == 3) cout << kth(l , r , x) << "\n";if(op == 4) cout << sum(l , r , x , y) << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

CF 896 C Willem, Chtholly and Seniorious(珂朵莉树模板)

CF 896 C. Willem, Chtholly and Seniorious(珂朵莉树模板) Problem - C - Codeforces 大意&#xff1a;给出一个区间 &#xff0c; 要求进行四种操作 &#xff0c; 区间加 &#xff0c; 区间第k大 &#xff0c; 区间推平 &#xff0c; 区间求和。 珂朵莉树模板题 &#xff…...

Android Jetpack组件的全方位分析

Jetpack是一个用于简化Android应用程序开发的工具包&#xff0c;包含了一系列的组件和工具。Jetpack包含了很多组件&#xff0c;如LiveData、ViewModel、Room、Data Binding、Navigation等。 Jetpack组件是一种更高级别的抽象&#xff0c;它们可以提供更简洁、更易于使用的API。…...

Prometheus+Grafana+AlertManager监控SpringBoot项目并发送邮件告警通知

文章目录 PrometheusGrafanaAlertManager监控平台搭建新建SpringBoot项目为Prometheus提供指标新建项目&#xff0c;引入依赖新建接口&#xff0c;运行程序 推送指标到pushgateway 开始监控Grafana连接Prometheus数据源导入Grafana模板监控SpringBoot项目 邮件告警通知同系列文…...

猿辅导Motiff亮相IXDC 2023国际体验设计大会,发布新功能获行业高度关注

近日&#xff0c;“IXDC 2023国际体验设计大会”在北京国家会议中心拉开序幕&#xff0c;3000设计师、1000企业、200全球商业领袖&#xff0c;共襄为期5天的用户体验创新盛会。据了解&#xff0c;此次大会是以“设计领导力”为主题&#xff0c;分享全球设计、科技、商业的前沿趋…...

【QT】重写QAbstractLIstModel,使用ListView来显示多列数据

qt提供了几个视图来进行信息的列表显示&#xff0c;QListView可以用来显示继承QStractListModel的字符串列表中的字符串&#xff0c;默认的模型里面只包含一列的内容&#xff1a; 这里以qml为例子&#xff0c;先新建一个qml的项目&#xff0c;示例代码如下&#xff1a; 先创建一…...

【从零学习python 】64. Python正则表达式中re.compile方法的使用详解

文章目录 re.compile方法的使用进阶案例 re.compile方法的使用 在使用正则表达式时&#xff0c;我们可以直接调用re模块的match、search、findall等方法&#xff0c;并传入指定的正则表达式进行匹配。另外&#xff0c;我们还可以使用re.compile方法生成一个正则表达式对象&…...

【FAQ】视频云存储/安防监控EasyCVR视频汇聚平台如何通过角色权限自行分配功能模块?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、…...

基于Spring Boot的社区诊所就医管理系统的设计与实现(Java+spring boot+MySQL)

获取源码或者论文请私信博主 演示视频&#xff1a; 基于Spring Boot的社区诊所就医管理系统的设计与实现&#xff08;Javaspring bootMySQL&#xff09; 使用技术&#xff1a; 前端&#xff1a;html css javascript jQuery ajax thymeleaf 微信小程序 后端&#xff1a;Java …...

mysql从传统模式切到GTID模式后启动主从,主从异常报错1236

一 前言 MySQL 的主从复制作为一项高可用特性&#xff0c;用于将主库的数据同步到从库&#xff0c;在维护主从复制数据库集群的时候&#xff0c;作为专职的MySQL DBA&#xff0c;笔者相信大多数人都会遇到“Got fatal error 1236 from master when reading data from binary …...

Qt+C++串口调试接收发送数据曲线图

程序示例精选 QtC串口调试接收发送数据曲线图 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对<<QtC串口调试接收发送数据曲线图>>编写代码&#xff0c;代码整洁&#xff0c;规则&…...

【从零学习python 】75. TCP协议:可靠的面向连接的传输层通信协议

文章目录 TCP协议TCP通信的三个步骤TCP特点TCP与UDP的区别TCP通信模型进阶案例 TCP协议 TCP协议&#xff0c;传输控制协议&#xff08;英语&#xff1a;Transmission Control Protocol&#xff0c;缩写为 TCP&#xff09;是一种面向连接的、可靠的、基于字节流的传输层通信协议…...

IPv4 基础概念

IPv4 基础概念 IPv4 广播地址 广播是一种通信方式&#xff0c;用于将数据包发送到同一网络中的所有设备。在广播中&#xff0c;数据包被发送到特殊的广播地址&#xff0c;例如在IPv4中&#xff0c;广播地址通常为特定子网的广播地址&#xff08;例如&#xff0c;192.168.1.0/…...

stm32片内读写项目总结(多字节读写tongxindu)

1.flash操作驱动程序 a头文件 #ifndef FLASH_H #define FLASH_H #include “stm32f4xx.h” #define BOARD_NUM_ADDR 0x0800C000 #define STM32_FLASH_BASE 0x08000000 //STM32 FLASH的起始地址 #define FLASH_WAITETIME 50000 //FLASH等待超时时间 //FLASH 扇区的起始地址…...

ECMAScript6 简介及拓展

ECMAScript简介 JavaScript是大家所了解的语言名称&#xff0c; 但它的正式名称叫做ECMAScript。 1996年11月&#xff0c; JavaScript的创造者网景公司将JavaScript提交给国际化组织 ECMA(欧洲计算机制造联合会)&#xff0c; 希望这种语言能够成为国际标准。 随后 ECMA 发布…...

可视化构建包分析报告

一、webpack 使用 webpack-bundle-analyzer 插件即可。 安装&#xff1a;npm install webpack-bundle-analyzer -D 使用&#xff1a;new BundleAnalyzerPlugin(options?: object) Name Type Description analyzerMode One of: server, static, json, disabled Default: se…...

统一git使用方法,git状态变迁图,git commit提交规范

目录 说明 统一git使用方法 git状态变迁图 git commit 提交规范 说明 多次工作中多名员工不懂git多次技术分享&#xff0c;自行查资料学习git并使用&#xff0c;会出现使用各种偏僻的命令&#xff0c;异常问题无法解决&#xff1b;或出现带url的git合并提交。主要是学的不…...

react与vue的区别

React和Vue.js是两个流行的JavaScript库/框架&#xff0c;用于构建用户界面。以下是React和Vue之间的一些主要区别&#xff1a; 学习曲线&#xff1a;Vue.js对于新手来说比React更容易学习和上手。 构建方式&#xff1a;React强调组件的可重用性&#xff0c;而Vue.js更注重模板…...

成功解决SQL 错误 [22000]: 第3 行附近出现错误: 试图修改自增列[ID](达梦数据库)

当我们使用工具来手动修改自增列的自增ID时&#xff0c;可能会报如下异常 SQL 错误 [22000]: 第3 行附近出现错误:试图修改自增列[ID] 解决办法&#xff1a; 可以使用SQL语句来修改 ALTER TABLE "fdw"."SYSTEM_DICT_TYPE" DROP IDENTITY; UPDATE "f…...

【算法】活用双指针完成复写零操作

Problem: 1089. 复写零 文章目录 题目解析算法原理分析找到最后一个复写的位置从后往前进行复写操作 代码展示 题目解析 首先我们来分析一下本题的题目意思 可以看到题目中给到了一个数组&#xff0c;意思是让我们将数组中的零元素都复写一遍&#xff0c;然后将其余的元素向后平…...

【面试高频题】难度 3/5,字典树热门运用题

题目描述 这是 LeetCode 上的 「745. 前缀和后缀搜索」 &#xff0c;难度为 「困难」。 Tag : 「字典树」 设计一个包含一些单词的特殊词典&#xff0c;并能够通过前缀和后缀来检索单词。 实现 WordFilter 类&#xff1a; WordFilter(string[] words) 使用词典中的单词 words 初…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...