题解SP3267【DQUERYDquery】

题目描述：

给出一串长度为 \(n\) 的序列，有 \(q\) 个询问，每次询问给数对 \((i,j)\)，求区间 \([i,j]\) 中有多少个不同的数字

这题我是用莫队过的；

众所周知，莫队是一个暴力毒瘤玄学很方便的算法（不套其他的数据结构），可以乱搞很多的区间问题。

p.s.我是通过这篇博客来自学的，如果有理解不对的地方，还望 dalao 指正

进入正题：

莫队算法将询问排序后，通过移动左右端点来更改答案，从而保证它优秀的复杂度。

在排序询问时，我们要用到分块的思想：

我们将整个区间分成 \(\sqrt{n}\) 个块。

在排序的时候，如果左端点在同一个块，就将右端点按从大到小排序；否则，按左端点的块从大到小排序。

这样保证了每个端点一次最多移动 \(\sqrt{n}\) 格，从而保证了复杂度。

friend bool operator <(qus a,qus b){
return k[a.l]==k[b.l]?a.r}

然后在排序的时候可以将普通的排序，换成按块的奇偶分类排序，可以让你的代码玄学咕咕咕的加快。

friend bool operator <(qus a,qus b){
return k[a.l]^k[b.l]?k[a.l]b.r);
}

之后便是 Add 和 Del 函数，用来在移动的同时更新答案。

用 num 来记录目前的区间 \([l,r]\) 的数字种类，\(cnt_x\) 来记录 x 出现的次数；

在加入第 pos 个数时，如果该数在这个区间第一次出现，则将总数加一：

void Add(int pos){
if(!cnt[a[pos]]) ++num;
++cnt[a[pos]];
}

在删除第 pos 个数时，如果删除后这个数在区间内不在出现，则将总数减一：

void Del(int pos){
--cnt[a[pos]];
if(!cnt[a[pos]]) --num;
}

然后是转移左右端点。

如果当前的左端点，小于答案的左端点，则将该点删除，并将左端点向右移；

如果当前的左端点，大于答案的左端点，则将左端点左移，并且将该点加入；

如果当前的右端点，大于答案的右端点，则将该点删除，并将右端点向左移；

如果当前的右端点，小于答案的右端点，这将右端点右移，并且将该点加入。

（这不是绕口令）

while(L while(L>q[i].l) Add(--L);
while(R while(R>q[i].r) Del(R--);

最后在统计答案的时候，按照原先输入的顺序输出就好了。

代码如下（码风有点丑）：

#include
#define rint register int
using namespace std;
inline int read(){
int s=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
return f?s:-s;
}
int n,a[30010],cnt[1000010],num=0,Q;
int k[1010],ks,ans[200010];
struct qus{
int l,r,id;
friend bool operator <(qus a,qus b){
return k[a.l]^k[b.l]?k[a.l]b.r);
}
}q[200010];
void Del(int pos){
--cnt[a[pos]];
if(!cnt[a[pos]]) --num;
}
void Add(int pos){
if(!cnt[a[pos]]) ++num;
++cnt[a[pos]];
}
int main(){
n=read(); ks=sqrt(n);
for(rint i=1;i<=n;++i) a[i]=read();
for(rint i=1;i<=n;++i) k[i]=(i-1)/ks+1;
Q=read();
for(rint i=1;i<=Q;++i){
q[i].l=read();
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+Q);
int L=1,R=0;
for(rint i=1;i<=Q;++i){
while(L while(L>q[i].l) Add(--L);
while(R while(R>q[i].r) Del(R--);
ans[q[i].id]=num;
}
for(rint i=1;i<=Q;++i)
printf("%d\n",ans[i]);
return 0;
}

咕咕咕~