SP3267 DQUERY - D-query（莫队算法，区间不同数）

本文主要是介绍SP3267 DQUERY - D-query（莫队算法，区间不同数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： 询问区间有多少个不同的数。

思路：
莫队裸题。
十分神奇的算法，我觉得关键就是离线排序，但是左端点的判据是第几块（分块），右端点的判据是大小。就这么一点点小改动，大大减小了复杂度ORZ。

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;const int maxn = 1e6 + 7;
int n,m,t,a[maxn],pos[maxn],L[maxn],R[maxn];
int ans[maxn],cnt[maxn],now;struct Node
{int l,r,id;
}nodes[maxn];int cmp(Node x,Node y)
{return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
}void init()
{t = sqrt(n*1.0);for(int i = 1;i <= t;i++){L[i] = t * (i - 1) + 1;R[i] = t * i;}if(R[t] < n){t++;L[t] = R[t - 1] + 1;R[t] = n;}for(int i = 1;i <= t;i++){for(int j = L[i];j <= R[i];j++){pos[j] = i;}}
}void add(int x)
{if(cnt[a[x]] == 0)++now;++cnt[a[x]];
}void del(int x)
{--cnt[a[x]];if(cnt[a[x]] == 0)--now;}int main()
{scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);init();scanf("%d",&m);for(int i = 1;i <= m;i++){scanf("%d %d",&nodes[i].l,&nodes[i].r);nodes[i].id = i;}sort(nodes + 1,nodes + 1 + m,cmp);int l = 1,r = 0;//l代表1~l-1都没有，r代表r+1~n都没有for(int i = 1;i <= m;i++){while(l < nodes[i].l)del(l++);while(l > nodes[i].l)add(--l);while(r < nodes[i].r)add(++r);while(r > nodes[i].r)del(r--);ans[nodes[i].id] = now;}for(int i = 1;i <= m;i++)printf("%d\n",ans[i]);return 0;
}