- hsfzbzjr's blog
带修改的莫队
- 2 years ago @
U11讲 笔记
带修改的莫队算法
表示 号问询依赖几次修改。
修改次数可以理解成时间戳
复杂度分析+最优分块大小
序列编号每组大小 ,序列共 组,平面共
移动 : 每两个问询间:左端点抖动距离不超过 ,左端点抖动总距离不超过
移动 : 块内每两个问询间:右端点抖动距离不超过 ,右端点抖动总距离不超过 ,跨越块列时总距离:
移动 : 每个块内总距离 : ,所有块总距离 :
总复杂度 : 额外排序:
等号条件 :
例一 KK3170 计数种类 1
题面
题目描述
有一个长度为 的正整数序列,共有 次操作,分为两种
代表询问你从第 个数到第 个数中共有几种不同的数字类型。
把第 个数字替换为数值
程序名 : category.cpp
输入格式 category.in
第一行包含正整数 和 。
接着一行为 个正整数,代表序列的初始值。
然后有 行,每行一条操作指令,保证都合法。
输出格式 category.out
对于每一个问询,输出一行包含一个整数
输入样例
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
输出样例
4
4
3
4
数据范围
序列中元素的数值范围是 到
Code
封装操作函数
封装后的核心代码
简化修改操作
修改只有两种可能:正向修改/反向撤销
且一定是交替发生
例二 KK3171 计数种类2
题面
题目描述
有一个长度为 的正整数数列,共有 次操作,分为两种:
代表问询你从第 个数到第 个数中出现次数所组成数集的 值
把第 个数字替换成数值
备注:在这里,一个整数集合的 值为最小的不在集合中的正整数
输入格式 classification.in
第一行包含正整数 和 。
接着一行为 个正整数,代表序列的初始值。
然后有 行,每行一条操作指令,保证都合法。
输出格式 classification.out
对于每一个问询,输出一行包含一个整数。
输入样例
10 4
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
1 2 8
输出样例
2
3
2
数据范围
数值范围是 到
算法分析
引理
答案范围不超过
证明
假设某一次问询的答案为 ,大于 ,那么根据 的定义,这段区间中数的个数至少为 但是区间长度不能超过 。因此假设不成立。
因此,答案并不会很大,可以维护一个计数器的计数器数组。
Code
离散化
核心代码
三个封装的函数
Homework
KK3170,KK3170