问题描述:
有 n 个数（其中有些数可能相同）摆成一排。有以下操作：
Q L R 查询：第 L ~ R 个数中有几个不同的数
R P Col 修改：把第 P 个数改成 Col
| 输入：第 1 行输入两个整数 n 和 m，分别代表初始数量和操作个数。第 2 行输入 n 个整数，代表初始数列。第 3 ~ 2 + m 行中，每行输入一种操作 |
| 输出：对于每个查询，输出一个数字，代表第 L ~ R 个数中有几个不同的数 |
| 输入样例 | 输出样例 |
| 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 |
单点修改 + 区间查询
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //加快执行效率
#define endl "\n"
using namespace std;
const int N = 1e6+ 10;
int n, m, mc, mq, len;
int o[N], f[N], st[N], res;
// 结果 标记
struct query{ // 记录询问的列表
int l, r, id, t;
}q[N];
struct modify{ // 记录修改操作的列表
int x, y;
}c[N];
inline int get(int a) // 得到块儿编号
{
return a / len;
}
inline void add(int a) // 增加
{
if(!st[a]) res ++;
st[a] ++;
}
inline void del(int a) // 删除
{
st[a] --;
if(!st[a]) res --;
}
bool cmp(query a, query b) // 排序
{
int ai = get(a.l), aj = get(a.r); //找到所属的块
int bi = get(b.l), bj = get(b.r);
if(ai != bi) return ai < bi; // 先按左端点块儿号
if(aj != bj) return aj < bj; // 再按右端点块儿号
return a.t < b.t; // 都相同，按时间
}
inline void sovle()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> o[i]; //录入序列
char op;
int a, b;
for(int i = 0; i < m; i ++)
{
cin >> op >> a >> b;
if(op == 'Q') q[++ mq ] = {a, b, mq, mc}; //录入查询操作
else c[++ mc] = {a, b}; //录入修改操作
}
len = pow(n, 0.666); //点击跳转到注释
stable_sort(q + 1, q + mq + 1, cmp); //按照规则排序
int now = 0, l = 1, r = 0;
for(int i = 1; i <= mq; i ++) //离线操作
{
int id = q[i].id, t = q[i].t;
while(r < q[i].r) add(o[++ r]);
while(r > q[i].r) del(o[r --]); // 更新右端点
while(l < q[i].l) del(o[l ++]);
while(l > q[i].l) add(o[-- l]); // 更新左端点
while(now < t) // 更新时间
{
now ++;
if(c[now].x <= r && c[now].x >= l) // 不在修改范围内，直接跳过
{
del(o[c[now].x]); //移除当前颜色
add(c[now].y); //添加更新后的颜色
}
swap(o[c[now].x], c[now].y); // 交换两个颜色
}
while(now > t)
{
if(c[now].x <= r && c[now].x >= l)
{
del(o[c[now].x]);
add(c[now].y);
}
swap(o[c[now].x], c[now].y);
now --;
}
f[id] = res; // 记录结果
}
for(int i = 1; i <= mq; i ++)
{
cout << f[i] << endl;
}
}
signed main(void) //防止爆int
{
IOS;
sovle();
return 0;
}
笔记：带修莫队在普通莫队的基础上加上了时间维度，右区间也分块排序，oi-wiki在“最优块长以及时间复杂度分析”里也对$n^\frac{2}{3}$做了详细的解释。
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_64468032/article/details/134268330
54行注释：
我们设序列长为 n，m个询问，t个修改，时间复杂度的表达公式：
$\sum_{i=1}^{n/s} \sum_{j=i+1}^{n/s} (qij\cdot s+t)$ ①
= ms + ($\frac{n}{s}$)2t ②
= ms + $\frac{n^2t}{s^2}$
注释：① 左端点i块，右端点j块，上限是$\frac{n}{s} $块
② $\sum_{i=1}^{n/s} \sum_{j=i+1}^{n/s}$ qij在实际操作里是m次查询，($\frac{n}{s}$)2t：所有的时间维
通过求导公式获取极小值，设：f(x) = ms + $\frac{n^2t}{s^2}$
f ‘(x) = (ms + $\frac{n^2t}{s^2}$)’
=m $\cdot$ (s)’ + $n^2$t $\cdot$ $(\frac{1}{s^2} )$’ 线性法则
=m $\cdot$ 1 + $n^2$t $\cdot$ (-2) $\cdot$ $\frac{1}{s^3}$ 导数表：幂运算
= m – $\frac{2n^2t}{s^3}$
得出：s = $\sqrt[3]{\frac{2n^2t}{m}} $ = $\frac{2^\frac{1}{3}n^\frac{2}{3}t^\frac{1}{3}}{m^\frac{1}{3}} $
求出极值后再验证是否为极小值，判断极值点左右邻域的导数值的正负。左+右-，为极大值点，左-右+，为极小值点。
设 s = $s_0$ + ε，ε ∈ R
f ‘($s_0$+ ε ) = m – $\frac{n^2t}{(s_0 + ε)^3}$
易证 ε > 0 时 f ‘($s_0$+ ε ) > 0，ε < 0 时 f ‘($s_0$+ ε ) < 0
满足了左-右+，为极小值点的条件，所以，s = $s_0$ 处确为最小
当块长取$\frac{n^\frac{2}{3}t^\frac{1}{3}}{m^\frac{1}{3}} $时，带入ms + $\frac{n^2t}{s^2}$ 式子当中：m · ($\frac{n^\frac{2}{3}t^\frac{1}{3}}{m^\frac{1}{3}} $) + $\frac{n^2t}{(\frac{n^\frac{2}{3}t^\frac{1}{3}}{m^\frac{1}{3}})^2}$
约分后得出2${n^\frac{2}{3}m^\frac{2}{3}}t^\frac{1}{3}$，当指数不超过2的时候可以忽略时间复杂度的系数，最优的时间复杂度就是O(${n^\frac{2}{3}m^\frac{2}{3}}t^\frac{1}{3}$)
如果n，n，t是同数量级的时间复杂度，那时间复杂度就是就O($n^\frac{5}{3}$)，但是实际操作，一般还是推荐用$n^\frac{2}{3}$设为块长
版权声明：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用。本文链接：https://oi-wiki.org/misc/modifiable-mo-algo/