# 优雅的暴力——莫队算法

### 分析

[L,R] 表示当前的区间, 则有以下四种情况

3. sub(L++) 表示减去当前区间最左一格的贡献
4. sub(R--) 表示减去当前区间最右一格的贡献

[1, 2], [n-1, n];

[1, 2], [n-1, n];

...

[1, 2], [n-1, n];

[1, 2], [n-1, n];

[1,2],[1,2],...,[1,2]

[n-1, n],[n-1,n],....,[n-1,n]

```int n, m, a[maxn], pos[maxn], ans[maxm], res; // pos[i] = j 含义是a[i]所在分块编号为j.a[1,..,n], m个询问, 长度为n的序列
struct Q
{
int l, r, id; // 该询问[l, r], 是第id个询问
} qs[maxm];

ilv md()
{
int sz = sqrt(n); // 块大小
for(re i = 1; i <= n; i++)
{
pos[i] = （i - 1） / sz + 1; // 分块
}
for(re i = 1; i <= m; i++)
{
qs[i].id = i; // 离线所有询问
}
sort(qs + 1, qs + m + 1, [](Q &x, Q &y) { // 排序所有询问
return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
});
int l = 1, r = 0; // 初始化 [l, r] 为一个空的闭区间.全局变量res维护的就是[l, r]内询问的值
for(re i = 1; i <= m; i++)
{
while(q[i].l > l) sub(l++);
while(q[i].r < r) sub(r--);
ans[q[i].id] = res;
}
for(re i = 1; i <= m; i++) // 输出答案
{
writeln(ans[i]);
}
}```

```//#include "stdafx.h"
//#define LOCAL
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 5e4;
int n, m, k, res, a[maxn], cnt[maxn], ans[maxn], pos[maxn], sz;
struct Q
{
int l, r, id;
} qs[maxn];

ilv kk(int i, int flag)
{
int t = cnt[a[i]];
cnt[a[i]] += flag;
res += SQUARE(cnt[a[i]]) - SQUARE(t);
}

signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
sz = sqrt(n * 1.0);
for (re i = 1; i <= n; i++)
{
pos[i] = (i - 1) / sz + 1;
}
for (re i = 1; i <= m; i++)
{
qs[i].id = i;
}
sort(qs + 1, qs + m + 1, [](Q &x, Q &y){
return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
});
int l = 1, r = 0;
for (re i = 1; i <= m; i++)
{
while(qs[i].l < l) kk(--l, 1);
while(qs[i].r > r) kk(++r, 1);
while(qs[i].l > l) kk(l++, -1);
while(qs[i].r < r) kk(r--, -1);
ans[qs[i].id] = res;
}
for (re i = 1; i <= m; i++) writeln(ans[i]);
flush();
return 0;
}```

ac情况

### 拓展

1. 不带修莫队（本文）
2. 带修莫队，一般是单点修改
3. 树上莫队
4. 在线（带修或不带修）莫队
5. 二维莫队
6. 二次离线莫队

0 条评论

• ### #628 DIV2 题解

组样例，每组给一个和个数 。将同一个序列重复次得到一个新序列，问可以从新序列中严格最长上升子序列长度为多少。

• ### 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

• ### 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...

• ### 开篇：预备知识---1

​ 大家好，好久不写博客了，久违的感觉。这篇文章是 C/C++ 程序设计专栏的第一篇文章。说实话这个专栏申请了有半年多了，但是到目前为止仍然没有文章产出，本来...

• ### HUST 1586 数字排列

1586 - 数字排列 时间限制：1秒 内存限制：128兆 91 次提交 36 次通过 题目描述现有n个k位的数字，你的任务是重新安排数字每一位的位置，使得...

• ### agc015E - Mr.Aoki Incubator(dp)

平面上有\$n\$个点，每个点都有一个位置\$x_i\$，和向右的速度\$v_i\$ 现在要求你对其中的一些点进行染色，当一个点被染色后，在无限距离内与它相遇的点也会被染...

• ### [Laravel] Laravel的基本数据库操作部分

使用DB类的静态方法select来查询数据库，DB::select()，参数：sql语句，参数值数组