题意：求一系列编号最少能变成区间使得区间内编号连续，比如1、2、5，把1和2放在一个区间，5放在一个区间，答案是2。给n个数每个数有一个编号，m次查询L到R区间的答案。
分析：莫队处理m个查询。增加：一个数两边都没有数，加入它相当于加入了一个独立区域，答案会加一，一个数两边都有数，加入它相当于把两边联合在一起，答案会减一。删除与增加相反。需要注意这里增加和删除不能够抵消，当出现增加和删除不能够抵消的情况要先把答案清零，然后更新为当前区间的贡献，再继续操作，具体看代码实现。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int t,n,m,l,r,res,siz;
int a[maxn],pos[maxn];
int ans[maxn],cnt[maxn];
struct Q{
int l,r,k;
bool friend operator<(const Q &a,const Q &b){
return pos[a.l] == pos[b.l] ? a.r < b.r:pos[a.l] < pos[b.l];
}
}q[maxn];
void add(int pos){
if (!a[pos]) return;
if (!cnt[a[pos]+1]&&!cnt[a[pos]-1]) res++;
if (cnt[a[pos]+1]&&cnt[a[pos]-1]) res--;
cnt[a[pos]]++;
}
void del(int pos){
if (!a[pos]) return;
cnt[a[pos]]--;
if (!cnt[a[pos]+1]&&!cnt[a[pos]-1]) res--;
if (cnt[a[pos]+1]&&cnt[a[pos]-1]) res++;
}
int main(){
scanf("%d",&t);
while (t--){
memset(cnt,0,sizeof cnt);
scanf("%d%d",&n,&m);
siz = sqrt(n);
for (int i = 1; i <= n; i++){
scanf("%d",&a[i]);
pos[i] = i/siz+1;
}
for (int i = 1; i <= m; i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].k = i;
}
sort(q+1,q+m+1);
l = 1, r = 0, res = 0;
for (int i = 1; i <= m; i++){
if (l > q[i].r || r < q[i].l){
res = 0;
while (l <= r) cnt[a[l++]] = 0;
l = q[i].l , r = q[i].l - 1;
while (r < q[i].r) add(++r);
ans[q[i].k] = res;
continue;
}
while (l < q[i].l) del(l++);
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (r > q[i].r) del(r--);
ans[q[i].k] = res;
}
for (int i = 1; i <= m; i++){
printf("%d
",ans[i]);
}
}
return 0;
}