莫队算法解决的问题

　　1.查询区间[L,R]上不同种类元素的数量，时间复杂度O(n*sqrt(n));

　　2.单点更新+查询

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

分类

　　1.带修莫队算法

　　2.普通莫队算法

　　3.树形莫队算法

步骤

　　1.记录所有查询(离线操作）

　　2.对于所有查询进行分块，然后在每个unit内排序

　　3.用l，r表示指针，进行对于指针所指的区域进行答案的记录

　　(如果存在单点更新，则为"带修莫队"，引入第三个指针TIM)

　　4.按照查询给出的顺序将答案排序，输出

模板

　　

题目

　　1.LUOGU P1903数颜色 （带修莫队）

　　2.LUOGU P1494小z的袜子 （莫队算法）

 

树形莫队还没学会，先去补LCA，补完再回来

　　

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄