download：Go实战仿百度云盘 实现企业级分布式云存储系统
云程序员，微服务，是最近几年一直被频频提到的热门词汇。本课程将通过Golang来实现一个支持断点续传和秒传的分布式云存储服务系统。课程中老师将手把手带你从快速构建“云存储”原型系统，到分块上传，到搭建访问阿里云，最后进行系统的微服务化，让你快速掌握架构传输性能和稳定性的优化过程，秒变云时代中第一代“云程序员”。
适合人群
课程适用于0-3年工作经验的，
对云端开发感兴趣的，
具备一定独立解决问题的在校学生以及码农们。
技术储备要求
熟悉Golang语法基础
有Linux开发基础，至少用过Linux系统
拥有基础的数据库、网络知识
引入
(\;)
由于标题没有强迫在线，所以莫队算法是将一切的讯问按一定次第排好序，并且一次讯问是以上一次讯问为根底。
我们能够把一次讯问(l,r)看作二维平面上的一个点((l,r))，那我们在两次讯问间(l,r)指针一共挪动的间隔，本质上是((l_1,r_1)),((l_2,r_2))间的曼哈顿间隔
但求最小哈密尔顿途径又是无法做到的。所以我们需求找到一个适宜的次第，使得两指针挪动的间隔尽可能的小。
(\;)
中心
(\;)
假定如今给定你一个长为(n)的序列，(m)次讯问，每次讯问求([l,r])这段区间不同数的数量。
(n,m\leq 10^5)
关于这个问题来说，用线段树是很难去维护的。由于区间不同数的数量并不能很轻松地由左右子区间转移而来。
思索将整个序列分块，每段长度为(\sqrt n)
这样每段讯问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字，右端点的位置作为第二关键字，将讯问区间排序。
依照莫队的思想，我们按此次第依次处置每一个区间，在两个指针的挪动的过程中维护一个数组cnt，表示每一个数呈现的次数。
若发现某个数cnt为由1减为0了，将答案减1，反之则加1
(\;)
时间复杂度
(\;)
我们发现算法中时间的瓶颈就在于，左右指针总共会挪动几次。我们分开来看：
(留意：这里我们假定m与n同阶)
左端点
(\;)
由于第一关键字是按左端点所在块排序的，所以左端点所在块是单调不降的。
关于目前左端点与上一个左端点同属一个块的状况：最多呈现(n)次，但每一次两个点之间挪动的间隔不超越(\sqrt n)
因而：(O(n\sqrt n))
关于目前左端点与上一个左端点不同属一个块的状况：最多呈现(\sqrt n)次，但每一次两个点之间挪动的间隔不超越(n)
因而：(O(n\sqrt n))
(\;)
右端点
(\;)
其位置作为第二关键字。因而若左端点有若干个位于同一个块中，此时右端点应该是单调不降的。
因而关于同一个块的左端点，右端点至多挪动(n)次，而总共有(\sqrt n)个块
因而：(O(n\sqrt n))
否则，若左端点不在同一个块中，右端点的位置就无法肯定了。这样一次右端点至多挪动(n)次
但这种状况至多呈现(\sqrt n)次
因而：(O(n\sqrt n))
(\;)
综上所述，莫队算法的时间复杂度为(O(n\sqrt n))
Code
#include <bits/stdc++.h>
const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块
return a.r < b.r; // 右端点所属位置
}
int main() {
scanf("%d", &n);
sq = (int)sqrt(n);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处置每个点所属块的编号
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
std::sort(b + 1, b + n + 1);
nn = std::unique(b + 1, b + n + 1) - b - 1;
for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
//----------------- 上面是离散化局部，不多赘述
scanf("%d", &m);
for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
std::sort(ask + 1, ask + m + 1, cmp);
int x = 0, y = 0, res = 0; //x,y维护的是不断在挪动两个指针
for(int i=1;i<=m;i++) {
int l = ask[i].l, r = ask[i].r; // l,r是当前讯问的两个左右端点
while(x < l) { // 左端点向右移，区间减少
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}
while(x > l) { // 左端点向左移，区间变大
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}
while(y < r) { // 右端点向右移，区间变大
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}
while(y > r) { // 右端点向左移，区间减少
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}
ans[ask[i].pos] = res; // 留意：i是排序后区间的编号，但并不是输入时讯问的编号
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}
有疑问加站长微信联系（非本文作者）
