[HNOI2009]梦幻布丁

news/2024/2/27 21:12:43

限制

        时间限制: 1 Sec 内存限制: 128 MB

题目描述

        N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。例如颜色分别为1,2,2,1的四个布丁一共有3段颜色。

输入

第一行是两个整数,分别表示布丁个数n和操作次数m。
第二行有n个整数,第i个整数表示第i个布丁的颜色a[i]。
接下来m行,每行描述一次操作。每行首先有一个整数op表示操作类型:

  • 若op=1,则后有两个整数 x, y,表示将颜色x的布丁全部变成颜色y。
  • 若op=2,则表示一次询问。

输出

针对第二类操作即询问,依次输出当前有多少段颜色。

样例输入

4 3
1 2 2 1
2
1 2 1
2

样例输出

3
1

样例解释

        初始时布丁颜色依次为1,2,2,1,三段颜色分别为[1,1],[2,3],[4,4]。一次操作后,布丁的颜色变为1,1,1,1,只有[1,4] 一段颜色。

数据范围

40%数据n * m <= 3e8
60%数据n * m <= 5e8
1 <= n,m <= 100000; 0 < Ai,x,y < 1000000

提示

不保证颜色的编号不大于n,也不保证x!=y,m不是颜色的编号上限。

分析

        可以用链表来存不同颜色的链表(c数组),用数组xyg来存另一个同颜色的链表,c数组来记录链表的头。

代码

#include<stdio.h>
int n,m,i,j,op,x,y,s,a[100005],xyg[100005],c[1000005];
int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;++i){scanf("%d",&a[i]);xyg[i]=c[a[i]],c[a[i]]=i;if(a[i]!=a[i-1]) ++s;}while(m--){scanf("%d",&op);if(op==1){scanf("%d%d",&x,&y);if(x==y) continue;for(i=c[x];i!=0;i=xyg[i]){if(a[i-1]==y) --s;if(a[i+1]==y) --s;}for(i=c[x];i!=0;i=xyg[i]) a[i]=y,j=i;xyg[j]=c[y],c[y]=c[x],c[x]=0;}else printf("%d\n",s);}return 0;
}

http://www.ppmy.cn/news/745913.html

相关文章

好看的字体:华康流风体

从这里看到的. 感觉这个流风体真好看. 看看下面的这个: 呵呵,漂亮吧. 下载地址:http://font.85888.com/soft/5575.html

修改Typora默认的字体为好看秀美的中文字体“华康手札体“

一 下载并安装"华康手札体W5P"字体 &#xff08;1&#xff09;下载方式&#xff1a; 1. 方式一 http://www.downcc.com/font/341067.html2.百度云链接&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/125Hh-tqWOy1Ht-GvD_P2MQ 提取码&#xff1a;z6ka 复制…

【内网穿透】Linux服务使用宝塔面板搭建网站,并内网穿透实现公网远程访问

文章目录 前言1. 环境安装2. 安装cpolar内网穿透3. 内网穿透4. 固定http地址5. 配置二级子域名6. 创建一个测试页面 转载自cpolar极点云文章&#xff1a;Linux使用宝塔面板搭建网站&#xff0c;并内网穿透实现公网访问 前言 宝塔面板作为简单好用的服务器运维管理面板&#xf…

如何批量将PDF转换为图片?

在生活工作中&#xff0c;我们会处理很多电子合同。这些电子合同一般是PDF格式&#xff0c;不但存储空间大&#xff0c;且预览起来不太便捷&#xff0c;需要我们转换为图片格式更方便预览。如果人工一一处理比较繁琐复杂&#xff0c;有没有什么方案可以快速将pdf转换为图片呢&a…

显卡超频很简单 RivaTuner使用教程

RivaTuner 应该许多网友都非常熟悉&#xff0c;它的超频功能非常强大&#xff0c;拥有一块好显卡&#xff0c;当然想看看究竟显卡能跑到什么程度咯&#xff0c;无论对于准备购买显卡还是需要超频的朋友来说&#xff0c;RivaTuner 都是必备品&#xff0c;购买显卡前可以使用它进…

腾讯首次发布行业大模型,大模型进入落地战

腾讯首次发布行业大模型&#xff0c;大模型进入落地战 6月19日&#xff0c;腾讯云在国家科技传播中心召开「行业大模型及智能应用技术峰会」。在峰会上&#xff0c;腾讯云首次公布了「腾讯云行业大模型」研究进展&#xff0c;其依托腾讯云TI平台打造行业大模型精选商店&#x…

[洛谷]B3601 [图论与代数结构 201] 最短路问题_1(负权)(spfa)

SPFA模板啦~ 直接上ACcode: #include<bits/stdc.h> using namespace std; //#define int long long #define inf 2147483647 const int N15e310,M2*N; int dis[N],head[N],cnt; bool vis[N]; int n,m; struct E {int to,w,next; } e[M]; queue<int>q; void add(in…

品牌低价监测要注意哪些方面

对于所有销售渠道的价格&#xff0c;品牌一般都会有相应的标准&#xff0c;比如会设置建议零售价&#xff0c;这也是为了渠道间的合理发展&#xff0c;让品牌能够长期更好的生存&#xff0c;所以设置了相应价格线的产品&#xff0c;品牌当然不想出现低价产品链接。所以针对价格…

短视频如何去水印,去水印,短视频去水印,去水印下载到本地

前言 短视频APP里虽然有保存视频的按钮&#xff0c;但这种方式保存的视频右下角有水印&#xff0c;并且这种方式不适用于电脑。 所以&#xff0c;写这篇文章来分享如何下载没有水印的视频到本地&#xff0c;** 此方法适用于手机 **&#xff0c;且不需要安装任何软件和插件。…

蓝叠模拟器去广告方法

蓝叠模拟器去广告方法 当前使用的版本是4.2版本&#xff0c;模拟器启动时右下角会有弹窗&#xff0c;模拟器主页面也会有应用推荐&#xff0c;十分的烦人&#xff0c;经过多番折腾&#xff0c;终于去除了这些烦人的推广 1.右下角弹窗 打开蓝叠模拟器的安装目录&#xff0c;找…

如何去掉视频上的水印文字?视频去水印方法大分享

我们在网上看到喜欢的视频&#xff0c;都会保存下来&#xff0c;经常能够看到保存下来的这些视频中都带有水印。这些带有水印的视频在后期的观看过程中&#xff0c;会很影响整个画面&#xff0c;所以我们在保存下来后&#xff0c;可以选择将视频中的水印去除。那么视频如何去水…

Appium连接夜神模拟器

1、先启动模拟器&#xff0c;将需要做自动化的软件包拖入模拟器中&#xff0c;会自动安装 2、终端里面运行adb connect 127.0.0.1:62001 3、查看设备信息&#xff0c;运行adb devices -l 4、获取appPackage&#xff0c;appActivity 5、启动appium&#xff0c;输入host&#xf…

Android连接夜神模拟器详细步骤

Android连接夜神模拟器详细步骤 做毕设用到了android stdio,好久不用也生疏了&#xff0c;记录一下。 &#xff08;1&#xff09;打开并运行夜神模拟器&#xff0c; &#xff08;2&#xff09;打开命令行窗口&#xff0c;winR,并输入cmd。 &#xff08;3&#xff09;找到并…

夜神安卓模拟器adb命令详解

一、如何找到adb&#xff1f; 安装夜神安卓模拟器后&#xff0c;电脑桌面会有“夜神模拟器”的启动图标&#xff0c;鼠标右键--打开文件所在的位置&#xff0c;就会进入***\Nox\bin&#xff0c;比如小编的路径是C:\Program Files (x86)\Nox\bin&#xff0c;然后可以在该路径下找…

Appium 连接夜神模拟器并启动

Appium 连接夜神模拟器并启动 1.adb连接夜神模拟器设置 参考以下链接进行相关设置链接: https://blog.51cto.com/u_15354476/5342062 设置完成可查到对应模拟器设备 2.Appiun连接夜神模拟器 启动appium&#xff0c;默认配置直接启动。点击右上角搜索按钮 添加以下参数值&am…

小视频去水印原理及其代码?

使用uview框架及其微信小程序云开发 仅供学习和交流&#xff0c; 首先讲一下原理 具体看下边 https://www.cnblogs.com/raicho/p/16025522.html 这个还是比较简单的&#xff0c;如果自己会一点后端&#xff0c;根据上面的步骤慢慢来&#xff0c;我这里为了省事&#xff0c;使用…

如何去除视频中的水印?视频去水印方法分享

怎么把视频中的水印给去除掉呢&#xff1f;当一个视频中有水印时&#xff0c;这会对它的观看体验产生负面影响。尤其当水印过于明显或阻碍了视频的内容时&#xff0c;将会对观众造成干扰和困扰。去除视频中的水印可以让观众专注于视频本身&#xff0c;提升观看体验和感受。给大…

你知道视频的水印怎么去吗?

我们都知道在网上下载的视频可能会出现带水印的情况&#xff0c;这些水印的分布不尽相同&#xff0c;有时候可能出现在角落&#xff0c;有时候也可能出现在视频的正中间&#xff0c;对视频的观看效果产生了一定的影响&#xff0c;那么这些视频的水印怎么去呢&#xff1f;不知道…

adb 连接夜神模拟器

1.启动夜神模拟器&#xff0c;设置->关于平板电脑->点击5次版本号 进入开发者模式 2. 运行cmd命令&#xff0c;cd到夜神安装目录&#xff0c;执行命令 nox_adb.exe connect 127.0.0.1:62001

视频去水印方法总结

视频去水印方法总结 从素材网站下载的视频大多都留有水印&#xff0c;使用这些视频对使用者有较大干扰&#xff0c;很不方便&#xff0c;需要运用一定的方法尽可能去掉。通过查阅资料&#xff0c;视频去水印有以下常见的几种方法&#xff1a; 对视频空间区域进行裁剪&#xff…
最新文章