本文主要是介绍HDU-4638-Group(莫队)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意：给你n个数字，m个要查询的区间。 查询的是l-r区间内有几段连续的数字。
样例解释：
1 - 5 有数字3 1 2 5 4.排一下序：1 2 3 4 5.连续。所以输出1。
2 - 4 有数字1 2 5 4.排一下序：1 2 4 5，1 2连续，4 5连续。所以输出2。
思路：2 - 4区间的ans。我们来推1-4.我们向左移动一位，多了一个3，我们看vis[3-1]和vis[3+1]（vis[2],vis[4]）是否出现过。如果都出现过那么ans–1；因为3将左右数字连接了起来（也就是将两段变成了一段所以要减一）。如果只出现过一个，那么不用变。如果一个也没出现过。那么ans+1；因为多了一个数字（一个独立的数字）。同理删除一个数的时候也是一样。
while(l > q[i].l) add(a[--l]);注意：对于莫队的板子要将上面的代码放到下面，因为对于第二个样例他会标记vis[3] = 1,事实上vis[3] = 0。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6+7;
int sum, n, m, k, ans[maxn], pos[maxn], vis[maxn], a[maxn], l, r, block;
struct node{int l, r, id; }q[maxn];
bool cmp(node a, node b){return pos[a.l] == pos[b.l] ? a.r < b.r : a.l < b.l;}
inline void add(int x)
{if(vis[x-1] && vis[x+1]) sum--;if(!vis[x-1] && !vis[x+1]) sum++;vis[x] = 1;
}
inline void del(int x)
{if(vis[x-1] && vis[x+1]) sum++;if(!vis[x-1] && !vis[x+1]) sum--;vis[x] = 0;
}int main()
{int n,m,t;scanf("%d",&t);while(t--){memset(vis,0,sizeof vis);scanf("%d%d",&n,&m);block = sqrt(n);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);pos[i] = i / block + 1;}for(int i = 0; i < m; i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id = i;}sort(q, q+m, cmp);int l = 1, r = 0;sum = 0;for(int i = 0; i < m; i++){while(r < q[i].r) add(a[++r]);while(r > q[i].r) del(a[r--]);while(l < q[i].l) del(a[l++]);while(l > q[i].l) add(a[--l]);ans[q[i].id] = sum;}for(int i = 0; i < m; i++)printf("%d\n",ans[i]);}return 0;
}
这篇关于HDU-4638-Group(莫队)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
