莫队算法总结专题训练2

莫队算法总结专题训练2

莫队算法总结&专题训练2

• • 回顾：
  • 3.练习题
  • • 普通练手题
    • 带修莫队
    • 树上莫队
    • 树上带修莫队

回顾：

上回我们在莫队算法总结&专题训练1讲解了莫队的一般套路以及各种优化方式，但那只是基础，接下来将会介绍莫队更多的用法。这篇博文将会讲述 带修莫队、树上莫队、树上带修莫队 的用法，在莫队算法总结&专题训练3 中将会讲述 回滚莫队/不删除莫队、莫队二次离线/第十四分块（前体） 的思路以及实现。同时总结将会写在 莫队算法总结&专题训练3 当中。

3.练习题

题单：

• 普通练手题
• CF220B Little Elephant and Array
• P2709 小 B 的询问
• P1494 [国家集训队]小 Z 的袜子
• 带修莫队
• P1903 [国家集训队]数颜色 / 维护队列
• 树上莫队
• SP10707 COT2 - Count on a tree II
• 树上带修莫队
• P4074 [WC2013]糖果公园
• 回滚莫队/不删除莫队
• AT1219 歴史の研究
• 莫队二次离线/第十四分块（前体）
• P4887 【模板】莫队二次离线（第十四分块(前体)）

普通练手题

这里的题目都比较简单，因此代码就少贴一点。只需要更改 del&add 函数即可。主函数几乎不需要改。

CF220B Little Elephant and Array

首先可以发现， a i > n a_i>n ai​>n 的数据完全没有用，因此 c n t cnt cnt 统计 a i < n a_i<n ai​<n 的数据即可。

其次需要注意，只有 c n t a i = a i cnt_{a_i}=a_i cntai​​=ai​ 的数据是有效数据，大于或小于都不行

知道了这些，就跟例题没什么两样了（见莫队算法总结&专题训练1）。

贴一下 del&add 函数：

void del(int x)
{if(a[x]>n) return ;if(cnt[a[x]]==a[x]) total--;cnt[a[x]]--;if(cnt[a[x]]==a[x]) total++;
}
void add(int x)
{if(a[x]>n) return ;if(cnt[a[x]]==a[x]) total--;cnt[a[x]]++;if(cnt[a[x]]==a[x]) total++;
}

P2709 小 B 的询问

简直模板。

当然这道题到目前为止没有 log ⁡ log log 级别的做法。

更新答案时有两种操作，一种手推公式更新，一种直接暴力先减掉 c n t x 2 cnt_x^2 cntx2​ 处理完之后再加回去，我采用的是第二种。

贴一下 del&add 函数：

void Delete(int x)
{sum-=cnt[a[x]]*cnt[a[x]];cnt[a[x]]--;sum+=cnt[a[x]]*cnt[a[x]];
}
void Add(int x)
{sum-=cnt[a[x]]*cnt[a[x]];cnt[a[x]]++;sum+=cnt[a[x]]*cnt[a[x]];
}

P1494 [国家集训队]小 Z 的袜子

这道题需要手推一下公式。

假设颜色为 a , b , c a,b,c a,b,c 的数据分别出现了 x , y , z x,y,z x,y,z 次，那么答案：

x × ( x − 1 ) 2 + y × ( y − 1 ) 2 + z × ( z − 1 ) 2 + . . . ( r − l ) × ( r − l + 1 ) 2 dfrac{frac{x times (x-1)}{2} + frac{y times (y-1)}{2} + frac{z times (z-1)}{2} +...}{frac{(r-l) times (r-l+1)}{2}} 2(r−l)×(r−l+1)​2x×(x−1)​+2y×(y−1)​+2z×(z−1)​+...​

= x 2 + y 2 + z 2 + . . . . . . − ( x + y + z + . . . ) ( r − l ) × ( r − l + 1 ) = dfrac{x^2+y^2+z^2+......-(x+y+z+...)}{(r-l) times (r-l+1)} =