题解 P3901 【数列找不同】

题解 P3901 【数列找不同】

这题居然没有p的莫队题解哦！那我来水一发呗

--------------------------------分割线-------------------------

题目描述：求[l,r]中数字是否互不相同

题目思路：发现题目似乎没说强制在线哦，那就可以离线了哎 于是就可以用 莫队
来水掉这道题啊

这道题是最基础不带修的序列莫队，适合莫队初学者

有关莫队可以参见我这道题的题解:

小b的询问 https://www.luogu.org/problemnew/show/P2709

代码：

var
n,k,m,l,r,j,i,p:longint;
ans:int64;
a,x,y,c,b,f:array[0..500005] of longint;
procedure sort(l,r:longint);
var
i,j,xx,yy,yyy:longint;
begin
i:=l;
j:=r;
xx:=x[(l+r) div 2];
yy:=y[(l+r) div 2];//多关键字排序
repeat
if i div p=j div p then//判断i，j是否在同一块内
begin
while (x[i]<xx) do
inc(i);
while (xx<x[j]) do
dec(j);
if not(i>j) then//别忘记交换3个而不是1个数组
begin
yyy:=x[i];
x[i]:=x[j];
x[j]:=yyy;
yyy:=y[i];
y[i]:=y[j];
y[j]:=yyy;
yyy:=c[i];
c[i]:=c[j];
c[j]:=yyy;
inc(i);
j:=j-1;
end;
end else//这部分作用同上
begin
while (y[i]<yy) do
inc(i);
while (yy<y[j]) do
dec(j);
if not(i>j) then
begin
yyy:=x[i];
x[i]:=x[j];
x[j]:=yyy;
yyy:=y[i];
y[i]:=y[j];
y[j]:=yyy;
yyy:=c[i];
c[i]:=c[j];
c[j]:=yyy;
inc(i);
j:=j-1;
end;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
readln(n,m);
p:=trunc(sqrt(n));//把序列分成sqrt(n)块
for i:=1 to n do read(a[i]);
for i:=1 to m do
begin
readln(x[i],y[i]);
c[i]:=i;//莫队作为离线算法，当然要保存每个询问啦
end;
sort(1,m);
l:=1;
r:=0;
ans:=0;
fillchar(b,sizeof(b),0);
for i:=1 to m do
begin//莫队基本思想(本人喜欢while)
while l>x[i] do begin dec(l); inc(b[a[l]]); if b[a[l]]=1 then inc(ans); end;
while r<y[i] do begin inc(r); inc(b[a[r]]); if b[a[r]]=1 then inc(ans); end;
while l<x[i] do begin dec(b[a[l]]); if b[a[l]]=0 then dec(ans); inc(l); end;
while r>y[i] do begin dec(b[a[r]]); if b[a[r]]=0 then dec(ans); dec(r); end;
if ans=r-l+1 then f[c[i]]:=1 else f[c[i]]:=0;//用f数组记录读进来时第1-n个答案
end;
for i:=1 to m do if f[i]=1 then writeln('Yes') else writeln('No');
end.