P1903 [国家集训队]数颜色 / 维护队列

    • 3.6K通过
    • 11.6K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 块状链表,块状数组,分块 莫队 WC/CTSC/集训队 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:

    1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

    2、 R P Col 把第P支画笔替换为颜色Col。

    为了满足墨墨的要求,你知道你需要干什么了吗?

    输入输出格式

    输入格式:

    第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。

    第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。

    第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。

    输出格式:

    对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

    输入输出样例

    输入样例#1: 复制
    6 5
    1 2 3 4 5 5
    Q 1 4
    Q 2 6
    R 1 2
    Q 1 4
    Q 2 6
    输出样例#1: 复制
    4
    4
    3
    4
    

    说明

    对于100%的数据,N≤50000,M≤50000,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

    本题可能轻微卡常数

    来源:bzoj2120

    本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。