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

LGP3201 [HNOI 2009] 梦幻布丁 学习笔记

LGP3201 [HNOI 2009] 梦幻布丁 学习笔记

\(\texttt{Luogu Link}\)

前言

能启发你学会启发式合并的入门题。

题意简述

给定一个长 \(n\) 的序列 \(A\)。请完成 \(m\) 个操作,分为两种:

  • 1 x y:对于所有 \(a_i=x\)\(i\),将 \(a_i\) 替换为 \(y\)
  • 2:询问序列现在由多少个极长同色连续段组成。

\(n,m\le 10^5\)\(a_i,x,y\le 10^6\)

做法解析

一个操作带来的影响是什么?首先,颜色 \(x\) 全部变成颜色 \(y\),意味着对于拥有该颜色的下标集合,\(S_x\) 并入 \(S_y\);然后,对于答案来说,答案只少不多,对于每一个原来形如 \(yyxx\)\(xxyy\) 的结构(也即每一个 \(x\)\(y\) 的邻接)答案会减少 \(1\)

挺简单,不是吗?我们直接维护这个下标集合 \(S_i\),然后对于每次修改,先统计 \(x\)\(y\) 的邻接次数,再合并它们。为了保证时间复杂度我们启发式地做:对着小集合里的每一个下标 idx 查大集合里面 .count(idx+1).count(idx-1),让小的集合往大的里面并。

好这就做完了。

代码实现

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5,MaxV=1e6+5;
int N,M,ans,A[MaxN],Opt,X,Y;
set<int> S[MaxV];
int main(){readis(N,M);for(int i=1;i<=N;i++)readi(A[i]),ans+=(A[i]!=A[i-1]),S[A[i]].insert(i);for(int i=1;i<=M;i++){readi(Opt);if(Opt==1){readis(X,Y);if(X==Y)continue;if(S[X].size()>S[Y].size())swap(S[X],S[Y]);for(int k : S[X])ans-=(S[Y].count(k+1)+S[Y].count(k-1));for(int k : S[X])S[Y].insert(k);S[X].clear();}if(Opt==2)writil(ans);}return 0;
}

后记

当然,这道题不需要线段树来合并。但是信息更复杂的时候就需要了。就比如 \(\texttt{LGP11193}\)

http://www.hskmm.com/?act=detail&tid=31484

相关文章:

  • 2025年石头纸设备/吹塑机厂家最新权威推荐榜:环保石头纸、碳酸钙石头纸、固废石头纸及挤出吹塑机、注射吹塑机、半导体清洗液瓶子吹塑机专业选购指南
  • AI技术新突破:图像编辑与浏览器智能体
  • PWN手的成长之路-16-OGeek2019-babyrop
  • 2025年掘进机厂家最新权威推荐榜:隧道掘进机、煤矿掘进机、岩石掘进机、盾构掘进机,专业实力与高效施工口碑之选
  • AI元人文:关于“价值原语博弈”的对话
  • 2025/10/15
  • 2025年冷却塔厂家最新权威推荐榜单:工业冷却塔、闭式冷却塔、横流式冷却塔、逆流式冷却塔专业制造商精选
  • 2025年法兰保护套厂家最新推荐排行榜:管道法兰保护罩,不锈钢法兰保护套,耐腐蚀法兰保护套公司精选
  • 2025年扒胎机厂家最新权威推荐榜:液压无损扒胎机,全自动扒胎机,汽保扒胎机,轮胎扒胎机,汽车扒胎机,大轮胎扒胎机,无损扒胎机,辽南扒胎机,小车扒胎机,立式扒胎机专业选购指南
  • 2025年中国太阳能板品牌TOP10(排行榜):格局巨变
  • 【第十五周】机器学习的学习笔记11 - 实践
  • 2025年冲压件厂家最新权威推荐榜:新能源/光伏/精密/异形/五金/铝/汽配/不锈钢/家具冲压件源头厂商实力解析
  • 2025年无锡公考考编培训机构最新权威推荐榜:事业单位/央企国企招录培训实力厂家精选指南
  • 2025年重庆短视频代运营与百度信息流推广公司综合推荐榜,拍摄/投流/获客/引流/剪辑/包年推广哪家好?
  • 2025年重庆短视频信息流投流/获客/巨量广告投放/拍摄/代运营推广公司推荐榜区域精选公司分享
  • 俄罗斯合作伙伴 Mobx,用 NocoBase 交付多场景方案
  • 2025年法兰罩厂家最新权威推荐榜:专业防护与精密制造,工业管道安全守护首选品牌
  • 2025 年公务员培训机构推荐榜:聚焦适配与服务,认准靠谱选择
  • IDM(Internet Download Managerv 6.38)破解版下载!IDM 下载器永久免费版!提升下载速度达5倍!安装及使用教程
  • 2025年数控滚齿机厂家最新权威推荐榜:高精度齿轮加工设备源头供应商,实力与口碑双重保障
  • 2025年太阳能板定制厂家终极推荐榜:揭秘 top 10 可靠选择
  • 2025年太阳能板厂家TOP企业品牌推荐,单晶硅/多晶硅/光伏层压板公司推荐
  • Flex布局
  • JVM调优 的大厂案例: 凌晨零点,一个 TODO,差点把我们整个部门抬走
  • 如何在AutoCAD中加载大型影像文件?
  • 2025年氧化镁厂家最新推荐排行榜,高纯氧化镁,活性氧化镁,医药级氧化镁,工业级氧化镁公司推荐
  • C 语言 - struct 关键字解析
  • 从0到1 精通 5大 GC日志:5万字 GC日志圣经,大厂看GC日志的10字口诀,再不用看不懂GC日志了
  • 京东面试:什么是 JIT,JIT什么优势?什么是 类的生命周期七个阶段 ?什么是 字节码增强?
  • 2025年阀门保温罩厂家最新推荐排行榜,工业阀门保温罩,管道阀门保温罩,定制阀门保温罩,高效节能阀门保温罩公司推荐