莫队
这里不讲莫队的思路,各路大神已经讲清楚了。我们讲一下如何卡常。
\(Status\ 1\)
把正常的莫队交上去,记录。
单个点\(1784ms\)。
\(Status\ 2\)
把每一次询问的右边界\(right[i]\)从小到大改为从打到小,快了了一点。注意要把数组开小点。
\(1522ms\)。
\(Status\ 3\)
如果分为\(trunc(sqrt(n))\)块不好,然后分别试着分为\(n/6\)和\(n/10\)块。
\(1178ms/795ms\)。
我们可以发现当\(div\)在这个时候时,越大,越快。记录。
\(Status\ 4\)
分别来看一下\(/20\)和\(/30\)的状态:
\(533ms/618ms\) 记录,整体没有\(/10\)的优越。
\(Status\ 5\)
综合以上,我们\(/15\)。
得出记录。
\(Code\)
// luogu-judger-enable-o2
varnode_num,i,j,n,m,l,r,sum,k:longint;num:array[-1..51000] of longint;id,left,right,recf,ans:array[-1..51000] of longint;bucket:array[-1..51000] of longint;procedure Sort(l,r:longint);
vari,j,s,t:longint;
begini:=l; j:=r; s:=(l+r) div 2;repeatwhile ((recf[i]<recf[s])or((recf[i]=recf[s])and(right[i]>right[s]))) do inc(i);while ((recf[j]>recf[s])or((recf[j]=recf[s])and(right[j]<right[s]))) do dec(j);if i<=j thenbegint:=recf[i]; recf[i]:=recf[j]; recf[j]:=t;t:=id[i]; id[i]:=id[j]; id[j]:=t;t:=left[i]; left[i]:=left[j]; left[j]:=t;t:=right[i]; right[i]:=right[j]; right[j]:=t;inc(i); dec(j);end;until i>=j;if i<r then Sort(i,r);if j>l then Sort(l,j);
end;function Locate(node:longint):longint;
beginif node mod node_num=0 thenexit(node div node_num);exit(node div node_num+1);
end;procedure Ready;
beginread(n,m,k);node_num:=n div 15;for i:=1 to n do read(num[i]);for i:=1 to m dobegin id[i]:=i; read(left[i],right[i]); recf[i]:=Locate(left[i]); end;Sort(1,m);
end;procedure add(x:longint);
begininc(bucket[x]);inc(sum,bucket[x]*2-1);
end;procedure dim(x:longint);
begindec(bucket[x]);dec(sum,bucket[x]*2+1);
end;beginReady;l:=1;r:=0;for i:=1 to m dobeginwhile r<right[i] do begin inc(r); add(num[r]); end;while r>right[i] do begin dim(num[r]); dec(r); end;while l<left[i] do begin dim(num[l]); inc(l); end;while l>left[i] do begin dec(l); add(num[l]); end;ans[id[i]]:=sum;end;for i:=1 to m dowriteln(ans[i]);
end.
