莫队算法模板 / p1494

前言

莫队算法是一个很好的离线算法（离线算法：查询与修改不同期），

它可以 O ( m n ) O(m \sqrt n) O(mn ​)时间进行查询，

它不像线段树那样有着较为严苛的前置条件，线段树要求待求量有着区间可加性

而莫队算法的前置条件是 O ( 1 ) O(1) O(1)进行区间转移：[L,R]->[L,R+1], [L,R]->[L,R-1] …等步长为一的转移

这个前置条件很宽松，甚至看到离线便可以主动向莫队这块靠

它的实现也并不困难，主要分为两个函数：modui()， move() 函数，

前者是算法主体，它首先对询问进行排序，第一关键字是 l 所在块编号，第二关键字是 r 大小，然后再初始化询问区间 interval0 = [0, -1], 再根据move函数单步区间转移，在 O ( n ) O(n) O(n)时间内获取第一个询问的ans，然后对后续查询进行区间转移，最后总转移时间为 O ( n n ) O(n \sqrt n) O(nn ​)

后者是单步区间转移的代价函数，直接对ans进行修改，不同的题会有不同的move()函数，这一部分也是能否做出题的关键，modui()函数则相对模板化，可直接调用，move()函数则更多需要一些推导

一、 例题 p1494

题目链接：洛谷p1494

二、 思路及代码 1. 思路

我们来思考一下move()函数，其余部分则直接套模板即可

这道题目我们将move()拆成了add()和del()，和一块比较乱

add(): [L, R] -> [L, R+1] ，我们将新增的袜子编号记为 i ，则 c[i] 的计数cnt[c[i]]++，那么答案的变化为 ( c n t [ c [ i ] ] + 1 2 ) − ( c n t [ c [ i ] ] 2 ) = c n t [ c [ i ] ] \Large{cnt[c[i]]+1 \choose 2}-{cnt[c[i]] \choose 2}=\small{cnt[c[i]]} (2cnt[c[i]]+1​)−(2cnt[c[i]]​)=cnt[c[i]]，

del()也类似，变化为 c n t [ c [ i ] ] − 1 {cnt[c[i]]-1} cnt[c[i]]−1

那么ok，剩余部分简单套模板即可

2. 代码

代码如下 ：

#include 
#include 
#include 
#define int long long
using namespace std;
const int maxn = 5e4 + 5;
int n, m, sqrtn;
int c[maxn];
int sum;
int cnt[maxn];
int ans1[maxn], ans2[maxn];
struct query {
  int l, r, id;
} q[maxn];
bool cmp(const query &a, const query &b) {
  if (a.l / sqrtn != b.l / sqrtn) return a.l