「Codeforces」771-div2 E. Colorful Operations

E. Colorful Operations

https://codeforces.com/contest/1638/problem/E

题目描述

给你一个数组,默认初始元素为 0 ,颜色为 1,有三种操作:

  • Color l r c:将 [l, r] 区间内的颜色修改为 c
  • Add c x:将所有颜色为 c 的元素增加 x
  • Query i:打印第 i 个元素

输入描述

输入的第一行包含两个整数n和q(1≤n,q≤106) — 数组的长度以及您必须执行的查询次数。

接下来的每一个q行包含以问题陈述中描述的形式给出的查询。

输出描述

打印 Query 的结果。

样例

#1

5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
2
5
3

#2

2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
7
7
8

提示

下面解释第一个样本测试。蓝色、红色和绿色分别代表颜色1,2和3。
1645166322574

解析

个人认为本题的难点主要是如何维护这个颜色,我一开始是想用一个结点内部维护一个 color 和 val 属性,表示每个结点的颜色和值,用的是线段树,后面我发现如果一个区间内的颜色不同,那么 color 到底应该填什么呢…,val 又表示啥呢?

当然,我这是普通的线段树模板而已,才学不久,看来还是我太菜了…

回到主题:

我们先考虑单点操作,三种操作如下:

  • Color x c:将元素 i 的颜色修改为 c
  • Add c x:将所有颜色为 c 的元素增加 x
  • Query i:打印第 i 个元素

首先我们需要一个 L a z y [ c o l o r ] Lazy[color] Lazy[color] 来保存每个颜色的总和,因为我们总不可能遍历每一个颜色为 c 的元素都增加 x 吧?这样效率很低,可以考虑先操作,等该数的颜色发生变化时,再去更新元素的值,这就是一个延迟操作的效果。

还需要一个 c o l o r [ i ] color[i] color[i] 保持元素 i 的颜色。

对于操作 2 来说: L a z y [ c ] + = x Lazy[c] += x Lazy[c]+=x

对于操作 3 来说: A [ x ] + L a z y [ c o l o r [ x ] ] A[x] + Lazy[color[x]] A[x]+Lazy[color[x]] (输出需要加上 Lazy ,这就是延迟)

对于操作 1 来说:

A [ x ] + = L a z y [ c o l o r [ x ] ] A[x] += Lazy[color[x]] A[x]+=Lazy[color[x]] (颜色准备发生改变,更新当前元素=>触发延迟操作)

c o l o r [ x ] = c color[x] = c color[x]=c (更新颜色)

A [ x ] − = L a z y [ c ] A[x] -= Lazy[c] A[x]=Lazy[c] (因为我们输出时,我们要保证 A [ x ] + L a z y [ c o l o r [ x ] ] A[x] + Lazy[color[x]] A[x]+Lazy[color[x]] ,因此需要减去 L a z y [ c ] Lazy[c] Lazy[c]

手动模拟一下:

【1】Add 1 7
【2】Query 1 7
【3】Add 2 4
【4】Query 2
【5】Color 1 2
【6】Query 1

====================
Lazy:  0 0 0
Color: 1 1 1
A:     0 0 0
====================
【1】Lazy[1] += 7
====================
Lazy:  7 0 0
Color: 1 1 1
A:     0 0 0
====================
【2】A[1] + Lazy[color[1]] // print 7
【3】Lazy[2] += 4
====================
Lazy:  7 4 0
Color: 1 1 1
A:     0 0 0
====================
【4】A[2] + Lazy[color[2]] // print 7
【5】A[1] += Lazy[color[1]]
     color[1] = 2
     A[1] -= Lazy[2]
====================
Lazy:  7 4 0
Color: 1 1 1
A:     7 0 0
--------------------
Lazy:  7 4 0
Color: 2 1 1
A:     7 0 0
--------------------
Lazy:  7 4 0
Color: 2 1 1
A:     3 0 0
====================
【6】A[1] + Lazy[color[1]] // print 7

明白了单点操作,回来看看区间操作:

采用线段树和LazyTag的方式来进行实现。

colorVal[color]:同上面的 Lazy

需要一个结点,里面维护如下元素:

  • same:该区间的所有元素是否相同
  • color:该结点的颜色,当 same 为 true 时,表示该区间内所有的颜色
  • lazy:懒标记,同时也作为该元素的值

对于操作 2 和 操作 3 来说,其实和单点的是一样。对于操作 1 来说也差不多。

对于操作 1:只修改同一种颜色的区间,否则就一定往下找,最后一个点一定为 true

AC Code

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    static final int MAX = 1000005;
    static long[] colorVal = new long[MAX];
    static Node[] T = new Node[MAX << 2];
    static int n, m;

    public static void main(String[] args) throws Exception {
        n = nextInt(); m = nextInt();
        build(1, 1, n);
        while(m-- != 0) {
            String opt = nextStr();
            if(opt.equals("Color")) update(1, nextInt(), nextInt(), nextInt());
            else if(opt.equals("Add")) colorVal[nextInt()] += nextInt();
            else if(opt.equals("Query")) {
                int v = nextInt();
                out.println(query(1, v, v));
            }
        }
        out.flush();
    }

    public static void build(int p, int start, int end) {
        T[p] = new Node(start, end);
        if(start == end) {
            T[p].color = 1;
            T[p].same = true;
            return;
        }
        int mid = (start + end) / 2;
        build(L(p), start, mid);
        build(R(p), mid + 1, end);
        pushUp(p);
    }

    public static void update(int p, int start, int end, int k) {
        // 只修改同一种颜色的区间,否则就一直往下找,最后一个点一定为 true
        if(start <= T[p].left && end >= T[p].right && T[p].same) {
            T[p].lazy += colorVal[T[p].color];
            T[p].color = k;
            T[p].lazy -= colorVal[T[p].color];
            return;
        }
        pushDown(p);
        int mid = (T[p].left + T[p].right) / 2;
        if(start <= mid) update(L(p), start, end, k);
        if(end > mid) update(R(p), start, end, k);
        pushUp(p);
    }

    public static long query(int p, int start, int end) {
        long res = 0;
        if(start <= T[p].left && end >= T[p].right)
            return T[p].lazy + colorVal[T[p].color];
        pushDown(p);
        int mid = (T[p].left + T[p].right) / 2;
        if(start <= mid) res += query(L(p), start, end);
        if(end > mid) res += query(R(p), start, end);
        return res;
    }

    public static void pushDown(int p) {
        // 因为我们修改的是同一种颜色的区间,因此也对同一种颜色的区间下传
        if(T[p].same) {
            T[L(p)].lazy += T[p].lazy;
            T[R(p)].lazy += T[p].lazy;
            T[L(p)].color = T[p].color;
            T[R(p)].color = T[p].color;
            T[p].lazy = 0;
        }
    }

    public static void pushUp(int p) {
        // 只更新同一种颜色的区间
        if(T[L(p)].same && T[R(p)].same && T[L(p)].color == T[R(p)].color) {
            T[p].same = true;
            T[p].color = T[R(p)].color;
        } else {
            T[p].same = false;
        }
    }

    public static int L(int p) { return p<<1; };
    public static int R(int p) { return p<<1|1; };

    public static int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }

    public static String nextStr() throws Exception {
        st.nextToken();
        return st.sval;
    }
}

class Node {
    int left, right;
    int color; // 该区间颜色
    long lazy; // lazyTag
    boolean same; // 该区间内的颜色是否完全相同
    public Node(int left, int right) {
        this.left = left;
        this.right = right;
    }
}

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

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

相关文章

SpringBoot整合Minio,一篇带你入门使用Minio

本文介绍SpringBoot如何整合Minio&#xff0c;解决文件存储问题 文章目录 前言环境搭建项目环境搭建添加依赖库yml配置 Docker安装minio 代码实现MiniConfigservicecontroller 测试 前言 参考链接&#xff1a; 官网 环境搭建 项目环境搭建 将minio单独封装成一个module&am…

LeetCode单链表OJ题目做题思路分享

目录 移除链表元素链表的中间节点链表中倒数第K个节点合并两个有序链表 移除链表元素 链接: link 题目描述&#xff1a; 思路分享&#xff1a; 我们上个博客分享了第一种方法&#xff0c;下面我们分析第二种方法&#xff1a;思路就是将每一个不等于我们要删除的值的节点依次尾…

如何快速获取已发表学术论文的期刊封面及目录(caj格式下载和caj转pdf)

目录 1 下载caj格式的封面和目录 2 CAJ格式的封面和目录转PDF格式 在进行职称评审或成果申报时&#xff0c;一般要求提交你发表的成果所在的期刊的当期封面和目录。本文就手把手带带你制作一个期刊目录。 重要提示&#xff1a;下载期刊封面和目录需要你有知网账号&#xff0…

Java读取Properties配置文件的6种方式

Java读取Properties的方式 项目结构&#xff1a;经典的maven项目结构 配置文件1和2内容一致&#xff1a; jdbc.drivercom.mysql.cj.jdbc.Driver jdbc.urlmysql://localhost:3306/database?useUnicodetrue&characterEncodingutf-8&serverTimezoneAsia/Shanghai jdbc.…

【深度学习】计算机视觉(13)——模型评价及结果记录

1 Tensorboard怎么解读&#xff1f; 因为意识到tensorboard的使用远不止画个图放个图片那么简单&#xff0c;所以这里总结一些关键知识的笔记。由于时间问题&#xff0c;我先学习目前使用最多的功能&#xff0c;大部分源码都包含summary的具体使用&#xff0c;基本不需要自己修…

找高清无水印视频素材,就上这9个网站。

推荐几个我的视频素材库&#xff0c;有免费、收费、商用&#xff0c;希望对大家有帮助&#xff01; 1、菜鸟图库 https://www.sucai999.com/video.html?vNTYwNDUx 菜鸟图库可以找到设计、办公、图片、视频、音频等各种素材。视频素材就有上千个&#xff0c;全部都很高清&…

unityt光线透射目标

介绍 在Unity中&#xff0c;光线透射目标通常指的是在场景中放置的一些物体&#xff0c;用于模拟光线从一个物体透过到另一个物体的效果。canvas子物体组件中&#xff0c;勾不勾选“光线透射目标”有什么区别&#xff1f; 方法 在Canvas子物体组件中勾选“光线透射目标”时&…

Python基础合集 练习17(类与对象)

class Dog: pass papiDog() print(papi) print(type(papi)) 构建方法 创建类过后可以定义一个特殊的方法。在python中构建方法是__init__(),init()必须包含一个self参数 class pig(): #def__init__(self) -> None&#xff1a; print(‘你好’) pipgpig() 属性和方法 cl…

C++好难(2):类和对象(上篇)

okay&#xff0c;从这里开始&#xff0c;就进入c比较难的部分了~啊啊啊&#xff01;&#xff01;&#xff01; (﹃ԅ) 坚持坚持啦 ~ ᵎ(•̀㉨•́)و ̑̑ 【本章目标】 1.面向过程和面向对象初步认识 2.类的引入 3.类的定义 4.类的访问限定符及封装 5.类的作用域 6.类的实…

(1)QT基础铺垫

目录 1.Qt特性 2. 新建项目 3. 工作目录与构建目录 4. 工作目录 4.1 .pro 项目配置文件 4.2 dialog.h 4.3 dialog.cpp 4.4 main.cpp 5. 帮助文档 6. 调试信息 1.Qt特性 Qt经常被当作是一个基于c语言的gui开发框架&#xff0c;但是这并不是qt的全部&#xff0c;除了开…

JavaWeb( 二 ) URL

1.4.URL统一资源定位符 URL代表Uniform Resource Locator 统一资源定位符&#xff0c;也叫 URL地址 。是用于标识和定位Web上资源的地址&#xff0c;通常用于在Web浏览器中访问网站和文件。 URL由若干部分组成&#xff0c;scheme:// host : port / path 例如&#xff1a; htt…

WxGL应用实例:绘制点云

WxGL附带了几个工具函数&#xff0c;其中read_pcfile用来解析.ply和.pcd格式的点云文件&#xff0c;该函数返回一个PointCloudData类实例&#xff0c;包含以下属性&#xff1a; PointCloudData.ok - 数据是否可用&#xff0c;布尔型PointCloudData.info - 数据可用性说明&…

《通过十几轮数据进行模型训练,实现精确的无创血糖测量的演绎学习》阅读笔记

目录 0 演绎学习 1 论文摘要 2 论文十问 3 论文亮点与不足之处 4 与其他研究的比较 5 实际应用与影响 6 个人思考与启示 参考文献 0 演绎学习 在本文中&#xff0c;DL指的是Deduction Learning&#xff0c;即演绎学习方法。该方法是一种机器学习方法&#xff0c;通过使…

简单毛概刷题网页制作 3.0(拖欠近一年版)

原因是大概一年之前学校的毛概期末刷题网站突然崩了&#xff0c;但是一直没有修复。当时眼看着复习时间逐渐被压缩&#xff0c;自己啥也做不了&#xff0c;遂自学前端完成毛概刷题网页一枚。 最早的毛概刷题网站仅仅是 1.0 版本&#xff08;传送门&#xff09;&#xff0c;功能…

STM32F4_USMART调试组件

目录 1. USMART是什么&#xff1f; 2. USMART的特点 3. USMART实现流程 4. USMART组件 5. 在usmart_config.c中添加想要被USMART调用的函数 6. 实验程序 6.1 main.c 6.2 usmart.c 6.3 usmart.h 7. USMART调试的优越性说明 1. USMART是什么&#xff1f; USMART 是 AL…

org.apache.poi 设置 Excel 单元格颜色 RGB

一、背景说明 在使用 org.apache.poi 导出 Excel 时&#xff0c;需要设置部分单元格的颜色。 可以使用方法&#xff1a;org.apache.poi.ss.usermodel.CellStyle.setFillForegroundColor() 和 org.apache.poi.ss.usermodel.CellStyle.setFillPattern() 来设置单元格的颜色和填…

低频量化之 可转债 配债数据及策略 - 全网独家

目录 历史文章可转债配债数据 待发转债&#xff08;进展统计&#xff09;待发转债&#xff08;行业统计&#xff09;待发转债&#xff08;5证监会通过&#xff0c;PE排序&#xff09;待发转债&#xff08;5证监会通过&#xff0c;安全垫排序&#xff09;待发转债&#xff08;5证…

【算法】一文彻底搞懂ZAB算法

文章目录 什么是ZAB 算法&#xff1f;深入ZAB算法1. 消息广播两阶段提交ZAB消息广播过程 2. 崩溃恢复选举参数选举流程 ZAB算法需要解决的两大问题1. 已经被处理的消息不能丢2. 被丢弃的消息不能再次出现 最近需要设计一个分布式系统&#xff0c;需要一个中间件来存储共享的信息…

Java 怎样实现代理模式,有什么优缺点

一、介绍 代理模式是一种常见的设计模式&#xff0c;它可以为其他对象提供一种代理以控制对这个对象的访问。代理对象具有与被代理对象相同的接口&#xff0c;客户端无需知道代理对象和被代理对象的区别。代理模式可以应用于各种不同的场景&#xff0c;例如远程代理、虚拟代理…

SpringBoot整合Mybatis-plus实现多级评论

在本文中&#xff0c;我们将介绍如何使用SpringBoot整合Mybatis-plus实现多级评论功能。同时&#xff0c;本文还将提供数据库的设计和详细的后端代码&#xff0c;前端界面使用Vue2。 数据库设计 本文的多级评论功能将采用MySQL数据库实现&#xff0c;下面是数据库的设计&…
最新文章