P1558 色板游戏
题目链接
题目要求实现区间覆盖修改以及区间数量查询,不难想到为线段树,而需要维护什么值来得到不同数的数量很难想,但是我们注意到颜色的数量最多只有30种,所以对于每一种颜色在一个区间中是否存在,我们可以使用线段树+状态压缩来解决这个问题
首先考虑pushup,这点很简单,只要将两个儿子节点的颜色状态或一下就可以
然后考虑pushdown,此处为颜色覆盖,所以对于每次修改只需要将原先的颜色状态直接覆盖为新的状态即可,包括lazy也是这样,这里注意lazy存的是要覆盖的颜色种类,而改变的时候是要先将1左移lazy个位置然后覆盖
ac代码:
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+10;
struct Tree
{int l,r;int sum,lazy;
}tr[N<<2];
int n,m,q;
string op;
int l,r,d;
int lowbit(int x){return x&-x;}
void change(int u,int lazy)
{tr[u].sum=1<<lazy;tr[u].lazy=lazy;
}
void pushup(int u)
{tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;
}
void pushdown(int u)
{if(tr[u].lazy){change(u<<1,tr[u].lazy);change(u<<1|1,tr[u].lazy);tr[u].lazy=0;}
}
void build(int u,int l,int r)
{if(l==r)tr[u]={l,r,1<<1,0};else {tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}
void modify(int u,int l,int r,int d)
{if(tr[u].l>=l&&tr[u].r<=r){change(u,d);return ;}pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)modify(u<<1,l,r,d);if(r>mid)modify(u<<1|1,l,r,d);pushup(u);
}
int query(int u,int l,int r)
{if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;pushdown(u);int mid=tr[u].l+tr[u].r>>1;int res=0;if(l<=mid)res|=query(u<<1,l,r);if(r>mid)res|=query(u<<1|1,l,r);return res;
}
void solve()
{cin>>n>>m>>q;build(1,1,n);while(q--){cin>>op>>l>>r;if(l>r)swap(l,r);if(op=="C"){cin>>d;modify(1,l,r,d);}else {int ans=query(1,l,r);int cnt=0;while(ans){cnt++;ans-=lowbit(ans);}cout<<cnt<<endl;}}
}
signed main()
{Mirai;int T=1;//cin>>T;while(T--){solve();}
}
相关文章:
P1558 色板游戏
题目链接 题目要求实现区间覆盖修改以及区间数量查询,不难想到为线段树,而需要维护什么值来得到不同数的数量很难想,但是我们注意到颜色的数量最多只有30种,所以对于每一种颜色在一个区间中是否存在,我们可以使用线段树…...
大数据概论
1、大数据概念 大数据(Big Data): 指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产 大数据主要解决,海量数据的采集、存储和分…...
数据库访问中间件--springdata-jpa的基本使用
二、单表SQL操作-使用关键字拼凑方法 回顾 public interface UserRepository extends JpaRepository<User,Integer> {User findByUsernameLike(String username); }GetMapping("/user/username/{username}")public Object findUserByUsername(PathVariable S…...
c++游戏制作指南(二):制作一个炫酷的启动界面(c++绘图)
🍿*★,*:.☆( ̄▽ ̄)/$:*.★* 🍿 🍟欢迎来到静渊隐者的csdn博文,本文是c游戏制作指南的一部🍟 🍕更多文章请点击下方链接🍕 🍨 c游戏制作指南dz…...
spring.config.location 手动指定配置文件文件
–spring.config.locationD:\javaproject\bangsun\ds-admin\ds-oper-mgr\src\main\resources\application.yml...
【uniapp 使用ECharts】
Uniapp可以使用ECharts进行数据可视化,需要按照以下步骤进行操作: 1. 安装ECharts插件 可以使用npm安装echarts插件,命令如下: npm install echarts --save2. 引入ECharts插件 在需要使用ECharts的页面中引入ECharts插件&…...
数据结构--线性表2-2
目录 一、线性表例题: 二、分配动态内存: 1.动态创建一个空顺序表的算法: 2.动态顺序表的插入算法: 3.动态顺序表的删除 三、线性表的链式表示和实现 例题1:创建链表并插入26个字母 例题2:在链表中取…...
利用openTCS实现车辆调度系统(一)系统介绍
系统介绍 openTCS简介 官方的回答: openTCS(开放式运输控制系统的缩写)是一种免费的控制系统软件,用于协调自动导引车(AGV)和移动机器人车队,例如在生产工厂中。 通常应该可以控制任何具有通信…...
销存管理系统ssm进销存仓库销售java jsp源代码mysql
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 销存管理系统ssm 系统有1权限:管理员 二…...
【Axure教程】移动端二级滑动选择器
今天教大家制作移动端二级滑动选择器的原型模板,该原型已全国一二级省市选择器为案例,因为该原型用中继器做的,所以制作完成之后使用也很方便,只需修改中继器表格里的内容即可 一、效果展示 1. 拖动选择 2. 快捷选择 【原型预览…...
PHP操作solr
1,php下载solr(索尔)扩展,phpinfo需要支持solr扩展. 2,安装 Solr。Solr 要求您的系统上有 Java。java –version,Java 的版本大于 1.6 3,下载solr,并安装 D:\solr。 开启solr命令:solr start 关闭solr命令:…...
leetcode 46. Permutations(排列)
返回数组nums中数字的所有可能的排列组合。 思路: 排列组合这种一般会想到DFS。 这个排列中每个数字只能用一次, 可用如下DFS流程 stack.push(num); dfs(nums, num); stack.pop();退出条件: 当stack的size和nums数组一样时,说…...
5、二叉树
二叉树遍历 递归序 public static void f(Node head) {if (head == null) {return;}f(head.left);f(head.right); }前中后遍历_递归 public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur…...
Doris比MySQL快的原因
简介 在数据存储和数据分析领域,MySQL和Doris是比较流行的数据库管理系统的代表。 在如今的大数据时代,数据量和数据分析的速度是很重要的。 在数据分析和数据处理中,Doris比MySQL快,这个问题一直是许多人关心的问题。 Doris的数…...
Prometheus + Grafana安装
Prometheus是一款基于时序数据库的开源监控告警系统,非常适合Kubernetes集群的监控。Prometheus的基本原理是通过HTTP协议周期性抓取被监控组件的状态,任意组件只要提供对应的HTTP接口就可以接入监控。不需要任何SDK或者其他的集成过程。这样做非常适合做…...
二十三种设计模式第二十一篇--解释器模式
解释器模式(Interpreter Pattern)是一种行为设计模式,它用于定义一种语言的语法结构和解释器,使得可以解释并执行特定的语法规则。该模式可以将复杂的语言表达式分解为更小的语法单元,并定义其解释过程。 解释器模式的…...
PHP8的数据类型转换-PHP8知识详解
什么是数据类型转换? 答:数据从一个类型转换成另外一个类型,就是数据类型转换。 在PHP8中,变量的类型就是由赋值决定的,也就是说,如果 string 赋值给 $var,然后 $var 的类型就是 string。之后…...
2023 电赛 E 题 K210 方案
第一章:K210 介绍 K210芯片是一款基于RISC-V架构的嵌入式人工智能芯片,具备低功耗、高性能的特点。它拥有强大的图像处理和机器学习能力,适用于边缘计算设备和物联网应用。为了方便开发者,K210芯片提供了丰富的外设接口ÿ…...
Python的正则表达式re模块的compile()方法有什么作用?
re模块是Python标准库中的正则表达式模块,它提供了对正则表达式的支持。re.compile()是re模块的一个方法,用于将正则表达式编译成可复用的正则对象。 正则表达式是用来匹配和处理文本模式的强大工具。当你需要在字符串中查找、替换或者提取符合特定模式…...
SQL 语句中 left join 后用 on 还是 where,区别大了!
目录 情况 小结 举例 情况 前天写SQL时本想通过 A left B join on and 后面的条件来使查出的两条记录变成一条,奈何发现还是有两条。 后来发现 join on and 不会过滤结果记录条数,只会根据and后的条件是否显示 B表的记录,A表的记录一定会显…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
