统计颜色Count Color(POJ2777)题解
有一个长度为L厘米板,L是一个正整数,所以我们可以把它均匀地划分成L个部分,分别从左到右编号为1,2……L,每一个部分长度都为1厘米。现在我们必须给每个部分涂色,一个部分一种颜色,要求完成以下两种操作: 1.“C A B C1”:表示从A部分到B部分涂上C1颜色。 2.“P A B”:表示从A部分到B部分涂了几种颜色。 在我们的日常生活中,我们有非常少几种颜色(红色,绿色,蓝色,黄色...),所以你可以假设不同颜色的总数T是非常少。简单地说,我们表示颜色的名称为颜色1,颜色2,…..颜色T。最初时候,这个厘米版都涂成颜色1。
思路
由于颜色很少,所以说可以给他状态压缩成一个数。
也就是支持一下几个操作:
1.区间或上1<<k
2.查询区间的或值
然后用线段树做就可以了。
懒标记更新有一点不一样。
// C++ includes used for precompiling -*- C++ -*-// Copyright (C) 2003-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>./** @file stdc++.h* This is an implementation file for a precompiled header.*/// 17.4.1.2 Headers// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
#endif// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif#if __cplusplus >= 201402L
#include <shared_mutex>
#endif#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
#include <memory_resource>
#include <string_view>
#include <variant>
#endif#if __cplusplus > 201703L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
#include <stop_token>
#include <semaphore>
#include <source_location>
#include <syncstream>
#include <version>
#endif
//以上为万能头(POJ不能直接用,差评)
using namespace std;
const int N = 1000010;
int w[N];
struct owl {int l, r, v, q;
} tr[N * 4];
void pushup(int u) {tr[u].v = tr[u << 1].v | tr[u << 1 | 1].v;
}
void pushdown(int u) {tr[u].q = 0;tr[u << 1].q = tr[u << 1 | 1].q = 1;tr[u << 1].v = tr[u << 1 | 1].v = tr[u].v;
}
void build(int u, int l, int r) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].v = 1;return ;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);
}
int query(int u, int l,int r) {if (tr[u].q){return tr[u].v;}if (tr[u].l >= l && tr[u].r <= r){return tr[u].v;}int mid = tr[u].l + tr[u].r >> 1;if (r <= mid){return query(u << 1,l,r);}else if (l > mid){return query(u << 1 | 1,l,r);}else{return query(u << 1,l,mid) | query(u << 1 | 1,mid + 1,r);}
}
void modify(int u, int l, int r, int v) {if (tr[u].q) {pushdown(u);}if (tr[u].l >= l && tr[u].r <= r) {tr[u].v = 1 << (v - 1);tr[u].q = 1;return ;}int mid = tr[u].l + tr[u].r >> 1;if (r <= mid){modify(u << 1,l,r,v);}else if (l > mid){modify(u << 1 | 1,l,r,v);}else{modify(u << 1,l,r,v);modify(u << 1 | 1,l,r,v);}pushup(u);
}
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int L,T,M;cin >> L >> T >> M;build(1,1,L);while (M -- ){char op;cin >>op;if (op == 'C'){int l,r,c;cin >> l >> r >> c;if (l> r){swap(l,r);}modify(1,l,r,c);}else{int l,r;cin >> l >> r;if (l > r){swap(l,r);}int t = query(1,l,r);
// cout << t << endl;int res = 0;for (int i = 0; i < T; i ++ ){if (t & ((1 << i))){res ++ ;}}cout << res << "\n";}}return 0;
}
相关文章:
统计颜色Count Color(POJ2777)题解
有一个长度为L厘米板,L是一个正整数,所以我们可以把它均匀地划分成L个部分,分别从左到右编号为1,2……L,每一个部分长度都为1厘米。现在我们必须给每个部分涂色,一个部分一种颜色,要求完成以下两…...
MySQL数据的增删改查(一)
目录 新增(create) 插入单条记录 插入多条记录 查询(retrieve) 查询所有列 查询特定列 查询字段为表达式 别名 去重 排序 按单列排序 按多列排序 使用表达式或别名排序 排序NULL值 条件查询 比较运算符 逻辑运算…...
国产文本编辑器EverEdit - 如何给小众语言开发大纲分析脚本
1 开发参考:小众语言如何开发大纲分析脚本 1.1 应用场景 在使用IDE进行代码开发时,代码中的变量、结构体、函数等,在大纲视图中都会显示出来,用户可以快速的了解当前文档的结构,以及快速跳转到函数、变量的声明位置。…...
【数据结构】线性数据结构——数组
1. 定义 数组是一种线性数据结构,由一组相同类型的元素组成,这些元素使用连续的内存空间存储。数组通过索引(下标)访问,每个元素的索引是固定的,从零开始递增。 2. 特点 顺序存储: 元素在内存…...
QT---------GUI程序设计基础
代码UI化设计(QT) 实例功能概述 假设我们要创建一个简单的计算器应用程序。该应用程序具有以下功能: 包含数字按钮(0-9)、操作符按钮(、-、*、/)、等于按钮()和清除按…...
2、Bert论文笔记
Bert论文 1、解决的问题2、预训练微调2.1预训练微调概念2.2深度双向2.3基于特征和微调(预训练下游策略) 3、模型架构4、输入/输出1.输入:2.输出:3.Learned Embeddings(学习嵌入)1. **Token Embedding**2. **Position Embedding**3…...
Linux之ARM(MX6U)裸机篇----7.蜂鸣器实验
一,蜂鸣器模块 封装步骤: ①初始化SNVS_TAMPER这IO复用为GPIO ②设置SNVS_TAMPPER这个IO的电气属性 ③初始化GPIO ④控制GPIO输出高低电平 bsp_beep.c: #include "bsp_beep.h" #include "cc.h"/* BEEP初始化 */ void beep_init…...
Zabbix 监控平台 添加监控目标主机
Zabbix监控平台是一个企业级开源解决方案,用于分布式系统监视和网络监视。它由Zabbix Server和可选组件Zabbix Agent组成,通过C/S模式(客户端-服务器模型)采集数据,并通过B/S模式(浏览器-服务器模型&#x…...
SpringCloud整合skywalking实现链路追踪和日志采集
1.部署skywalking https://blog.csdn.net/qq_40942490/article/details/144701194 2.添加依赖 <!-- 日志采集 --><dependency><groupId>org.apache.skywalking</groupId><artifactId>apm-toolkit-logback-1.x</artifactId><version&g…...
html文件通过script标签引入外部js文件,但没正确加载的原因
移动端H5应用,html文件通过script标签引入外部js文件,但没正确加载,在移动设备上难以排查。通过PC浏览器打开,发现js被阻止了:blocked:mixed-content。 原因在于: “blocked:mixed - content” 是浏览器的…...
OpenHarmony开发板环境搭建
程序员Feri一名12年的程序员,做过开发带过团队创过业,擅长Java相关开发、鸿蒙开发、人工智能等,专注于程序员搞钱那点儿事,希望在搞钱的路上有你相伴!君志所向,一往无前! 0.OpenHarmony 0.1 OpenHarmony OpenHarmony是一款面向全场景、全连接、全智能的…...
【Rust自学】7.6. 将模块拆分为不同文件
喜欢的话别忘了点赞、收藏加关注哦(加关注即可阅读全文),对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 7.6.1. 将模块的内容移动到其他文件 如果在模块定义时模块名后边跟的是;而不是代码块&#…...
Python入门:8.Python中的函数
引言 在编写程序时,函数是一种强大的工具。它们可以将代码逻辑模块化,减少重复代码的编写,并提高程序的可读性和可维护性。无论是初学者还是资深开发者,深入理解函数的使用和设计都是编写高质量代码的基础。本文将从基础概念开始…...
MySQL什么情况下会加间隙锁?
目录 一、使用范围条件查询 二、唯一索引的范围查询 三、普通索引的查询 四、间隙锁的锁定规则 五、间隙锁的影响 间隙锁(Gap Lock)是MySQL中的一种锁机制,主要用于防止幻读现象。在MySQL的InnoDB存储引擎中,当事务隔离级别设置为可重复读(Repeatable Read)时,间隙…...
【服务器开发及部署】code-server 显示git graph
在开发一些linux上的内容的时候进程需要在开发机和生产部署上花费大量的时间。 为了解决上述问题,我们今天介绍一款在服务上开发的思路 git + code server + 宝塔 其中需要处理一些问题,此处都有交代 步骤 安装宝塔安装code-server配置插件配置浏览器处理的问题 git版本过低,…...
Linux 终端查看 nvidia 显卡型号
文章目录 写在前面1. 需求描述2. 实现方法方法一:方法二方法三: 参考链接 写在前面 自己的测试环境: Ubuntu20.04 1. 需求描述 Linux 终端查看 nvidia 显卡型号 2. 实现方法 方法一: 执行下列指令: sudo update…...
助你通过AI培训师中级考试的目录索引
嘿,各位看官!在您正式踏入接下来的知识小宇宙之前,咱先唠唠几句… 家人们,我跟你们说,我脑一热报名了那个 AI 培训师考试。本想着开启一场知识的奇幻之旅,结果呢,学视频内容的时候,那…...
百度PaddleSpeech识别大音频文件报错
一、背景 公司前同事留下了一套语音识别项目,内部使用百度PaddleSpeech。在项目验收的时候发现无法识别大音频文件,但是可以识别小音频文件。 这套项目是通过python调用的百度PaddleSpeech,然后提供了restful接口,然后java项目可…...
Lucene 漏洞历险记:修复损坏的索引异常
作者:来自 Elastic Benjamin Trent 有时,一行代码需要几天的时间才能写完。在这里,我们可以看到工程师在多日内调试代码以修复潜在的 Apache Lucene 索引损坏的痛苦。 做好准备 这篇博客与往常不同。它不是对新功能或教程的解释。这是关于花…...
RabbitMQ基础篇之快速入门
文章目录 一、目标需求二、RabbitMQ 控制台操作步骤1.创建队列2.交换机概述3.向交换机发送消息4.结果分析5.消息丢失原因 三、绑定交换机与队列四、测试消息发送五、消息查看六、结论 一、目标需求 新建队列:创建 hello.queue1 和 hello.queue2 两个队列。消息发送…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
