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

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 色板游戏

题目链接 题目要求实现区间覆盖修改以及区间数量查询&#xff0c;不难想到为线段树&#xff0c;而需要维护什么值来得到不同数的数量很难想&#xff0c;但是我们注意到颜色的数量最多只有30种&#xff0c;所以对于每一种颜色在一个区间中是否存在&#xff0c;我们可以使用线段树…...

大数据概论

1、大数据概念 大数据(Big Data): 指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合&#xff0c;是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产 大数据主要解决&#xff0c;海量数据的采集、存储和分…...

数据库访问中间件--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++绘图)

&#x1f37f;*★,*:.☆(&#xffe3;▽&#xffe3;)/$:*.★* &#x1f37f; &#x1f35f;欢迎来到静渊隐者的csdn博文&#xff0c;本文是c游戏制作指南的一部&#x1f35f; &#x1f355;更多文章请点击下方链接&#x1f355; &#x1f368; c游戏制作指南&#x1f3…...

spring.config.location 手动指定配置文件文件

–spring.config.locationD:\javaproject\bangsun\ds-admin\ds-oper-mgr\src\main\resources\application.yml...

【uniapp 使用ECharts】

Uniapp可以使用ECharts进行数据可视化&#xff0c;需要按照以下步骤进行操作&#xff1a; 1. 安装ECharts插件 可以使用npm安装echarts插件&#xff0c;命令如下&#xff1a; npm install echarts --save2. 引入ECharts插件 在需要使用ECharts的页面中引入ECharts插件&…...

数据结构--线性表2-2

目录 一、线性表例题&#xff1a; 二、分配动态内存&#xff1a; 1.动态创建一个空顺序表的算法&#xff1a; 2.动态顺序表的插入算法&#xff1a; 3.动态顺序表的删除 三、线性表的链式表示和实现 例题1&#xff1a;创建链表并插入26个字母 例题2&#xff1a;在链表中取…...

利用openTCS实现车辆调度系统(一)系统介绍

系统介绍 openTCS简介 官方的回答&#xff1a; openTCS&#xff08;开放式运输控制系统的缩写&#xff09;是一种免费的控制系统软件&#xff0c;用于协调自动导引车&#xff08;AGV&#xff09;和移动机器人车队&#xff0c;例如在生产工厂中。 通常应该可以控制任何具有通信…...

销存管理系统ssm进销存仓库销售java jsp源代码mysql

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 销存管理系统ssm 系统有1权限&#xff1a;管理员 二…...

【Axure教程】移动端二级滑动选择器

今天教大家制作移动端二级滑动选择器的原型模板&#xff0c;该原型已全国一二级省市选择器为案例&#xff0c;因为该原型用中继器做的&#xff0c;所以制作完成之后使用也很方便&#xff0c;只需修改中继器表格里的内容即可 一、效果展示 1. 拖动选择 2. 快捷选择 【原型预览…...

PHP操作solr

1&#xff0c;php下载solr(索尔)扩展&#xff0c;phpinfo需要支持solr扩展. 2&#xff0c;安装 Solr。Solr 要求您的系统上有 Java。java –version&#xff0c;Java 的版本大于 1.6 3&#xff0c;下载solr,并安装 D:\solr。 开启solr命令&#xff1a;solr start 关闭solr命令:…...

leetcode 46. Permutations(排列)

返回数组nums中数字的所有可能的排列组合。 思路&#xff1a; 排列组合这种一般会想到DFS。 这个排列中每个数字只能用一次&#xff0c; 可用如下DFS流程 stack.push(num); dfs(nums, num); stack.pop();退出条件&#xff1a; 当stack的size和nums数组一样时&#xff0c;说…...

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快的原因

简介 在数据存储和数据分析领域&#xff0c;MySQL和Doris是比较流行的数据库管理系统的代表。 在如今的大数据时代&#xff0c;数据量和数据分析的速度是很重要的。 在数据分析和数据处理中&#xff0c;Doris比MySQL快&#xff0c;这个问题一直是许多人关心的问题。 Doris的数…...

Prometheus + Grafana安装

Prometheus是一款基于时序数据库的开源监控告警系统&#xff0c;非常适合Kubernetes集群的监控。Prometheus的基本原理是通过HTTP协议周期性抓取被监控组件的状态&#xff0c;任意组件只要提供对应的HTTP接口就可以接入监控。不需要任何SDK或者其他的集成过程。这样做非常适合做…...

二十三种设计模式第二十一篇--解释器模式

解释器模式&#xff08;Interpreter Pattern&#xff09;是一种行为设计模式&#xff0c;它用于定义一种语言的语法结构和解释器&#xff0c;使得可以解释并执行特定的语法规则。该模式可以将复杂的语言表达式分解为更小的语法单元&#xff0c;并定义其解释过程。 解释器模式的…...

PHP8的数据类型转换-PHP8知识详解

什么是数据类型转换&#xff1f; 答&#xff1a;数据从一个类型转换成另外一个类型&#xff0c;就是数据类型转换。 在PHP8中&#xff0c;变量的类型就是由赋值决定的&#xff0c;也就是说&#xff0c;如果 string 赋值给 $var&#xff0c;然后 $var 的类型就是 string。之后…...

2023 电赛 E 题 K210 方案

第一章&#xff1a;K210 介绍 K210芯片是一款基于RISC-V架构的嵌入式人工智能芯片&#xff0c;具备低功耗、高性能的特点。它拥有强大的图像处理和机器学习能力&#xff0c;适用于边缘计算设备和物联网应用。为了方便开发者&#xff0c;K210芯片提供了丰富的外设接口&#xff…...

Python的正则表达式re模块的compile()方法有什么作用?

re模块是Python标准库中的正则表达式模块&#xff0c;它提供了对正则表达式的支持。re.compile()是re模块的一个方法&#xff0c;用于将正则表达式编译成可复用的正则对象。 正则表达式是用来匹配和处理文本模式的强大工具。当你需要在字符串中查找、替换或者提取符合特定模式…...

SQL 语句中 left join 后用 on 还是 where,区别大了!

目录 情况 小结 举例 情况 前天写SQL时本想通过 A left B join on and 后面的条件来使查出的两条记录变成一条&#xff0c;奈何发现还是有两条。 后来发现 join on and 不会过滤结果记录条数&#xff0c;只会根据and后的条件是否显示 B表的记录&#xff0c;A表的记录一定会显…...

智慧卤味,一码追溯:万界星空MES方案

一、行业痛点与MES目标1、主要痛点生产依赖经验&#xff1a;卤制时间、温度、配料比例依赖人工经验&#xff0c;产品口味和质量不稳定。追溯困难&#xff1a;一旦出现食品安全问题&#xff0c;难以快速精准追溯到问题源头&#xff08;原料批次、生产环节、操作人员等&#xff0…...

告别GDAL依赖!用Rasterio和TensorFlow 2.6搞定BigEarthNet-MM数据集划分与TFRecord转换

告别GDAL依赖&#xff01;用Rasterio和TensorFlow 2.6搞定BigEarthNet-MM数据集划分与TFRecord转换 在遥感图像处理领域&#xff0c;BigEarthNet-MM数据集因其多模态特性&#xff08;Sentinel-1 SAR和Sentinel-2 MSI数据&#xff09;成为研究热点。但许多开发者在处理该数据集时…...

企业微信考勤自动化解决方案:基于EasyWeChat的实战指南

企业微信考勤自动化解决方案&#xff1a;基于EasyWeChat的实战指南 【免费下载链接】easywechat &#x1f4e6; 一个 PHP 微信 SDK 项目地址: https://gitcode.com/gh_mirrors/ea/easywechat 在数字化办公普及的今天&#xff0c;企业考勤管理面临着数据采集繁琐、统计分…...

升级版会议纪要录音转文字工具 识别准转得快 整理省事体验好

前前后后踩过不下10款录音转写工具的坑&#xff0c;要么错字多到要逐行改&#xff0c;要么转出来的内容逻辑混乱&#xff0c;得花好几个小时捋顺&#xff0c;直到用到2026升级版的会议纪要录音转文字工具&#xff0c;才真的感受到什么叫识别准、转得快、整理省事体验好。今早开…...

TextInput Effects部署与测试:确保跨平台兼容性的完整流程

TextInput Effects部署与测试&#xff1a;确保跨平台兼容性的完整流程 【免费下载链接】react-native-textinput-effects Text inputs with custom label and icon animations for iOS and android. Built with react native and inspired by Codrops. 项目地址: https://git…...

计算机图形学面试突击:Cohen-Sutherland编码裁剪的10种边界情况详解

计算机图形学面试突击&#xff1a;Cohen-Sutherland编码裁剪的10种边界情况详解 在计算机图形学的面试中&#xff0c;直线段裁剪算法是高频考点之一。Cohen-Sutherland算法作为经典解决方案&#xff0c;其核心在于通过编码和位运算快速判断线段与裁剪窗口的关系。本文将深入剖析…...

H5页面如何优雅跳转iOS App Store?解决点击后二次跳转的坑

H5页面如何优雅跳转iOS App Store&#xff1f;解决点击后二次跳转的坑 在移动互联网时代&#xff0c;H5页面与原生App的无缝衔接已经成为提升用户体验的关键环节。特别是对于电商、社交、内容平台等需要引导用户下载App的场景&#xff0c;如何实现从H5页面到iOS App Store的平…...

大模型二面:请比较一下两个流行的Agent开发框架,LangChain和LlamaIndex。它们的核心应用场景有何不同?

1. 题目分析这道题从表面上看是在问两个框架的区别&#xff0c;但其实你要搞清楚的是两个问题&#xff1a;你在实际项目中做过技术选型吗&#xff1f;你知道什么场景该用什么框架吗&#xff1f; 如果你只是把两个框架的功能列表背一遍&#xff0c;那只能证明你看过文档。而你真…...

ROS与Webots协同开发:舵轮底盘运动控制实战解析

1. 舵轮底盘的核心原理与结构设计 舵轮底盘作为全向移动机器人的核心部件&#xff0c;其独特之处在于每个轮子都具备独立转向和驱动的能力。这种设计使得机器人能够在平面内实现任意方向的平移和旋转&#xff0c;完全突破了传统差速底盘的运动限制。我曾在物流AGV项目中实测过&…...

威联通NAS安全防护全攻略:10个必做设置让你的数据固若金汤

威联通NAS安全防护全攻略&#xff1a;10个必做设置让你的数据固若金汤 在数字化时代&#xff0c;数据安全已成为个人和企业最关注的议题之一。威联通NAS作为专业级网络存储设备&#xff0c;凭借其强大的硬件性能和丰富的软件生态&#xff0c;成为许多用户存储重要数据的首选。然…...