先知道這道題目的所求

• 求出一個 \(num_i\) 使 \(a\leq num_i\leq b\) 且在 \(l\leq place_i\leq r\)。然后統計 \(num_i\) 的個數。

• 求出一個 \(num_i\) 使 \(a\leq num_i\leq b\) 且在 \(l\leq place_i\leq r\)。然后統計 \(num_i\) 存在過。(不同于上一問的是這里只是 $inc(ans) $,而上一問是 \(inc(ans,num_i\)在區間里出現的次數) )。

明白所求之后開始做題。我們可以用莫隊來維護每一次的 \(l,r\) 之間的狀態,然后用分塊進行修改。分塊維護的是權值,并且維護上面的兩個數。

procedure add(x,i:longint); // 增加一個數 begininc(block[x,1]); inc(intersum[Locate(x),1]); // 出現次數++if block[x,1]=1 then begin block[x,2]:=1; inc(intersum[Locate(x),2]); end; // 有出現過,只可能是 1 或 0 表示出現或者沒有出現 end;procedure dim(x,i:longint); // 減少一個數字 begindec(block[x,1]); dec(intersum[Locate(x),1]);if block[x,1]=0 then begin block[x,2]:=0; dec(intersum[Locate(x),2]); end; end;

可能大家會問為什么分塊,其實上面幾篇題解講得不對,因為分塊的單點修改是 \(O(1)\) 的,而樹狀數組什么的是 \(O(\log\ n)\),會導致時間復雜度下降為 \(O(n\sqrt{n}\log\ n)\),將近 \(4e8\)。所以并不是方便才用的。

以下的就非常簡單了。

// luogu-judger-enable-o2 varblock_num,node_num,sum,i,j,n,m,l,r:longint;num,id,left,right,vall,valr,recf:array[-1..110000] of longint;block:array[-1..110000,1..2] of longint;intersum:array[-1..400,1..2] of longint;ans:array[-1..110000,1..2] of longint;procedure Swap(var x,y:longint); var t:longint; begin t:=x; x:=y; y:=t; end;function Locate(node:longint):longint; begin if node mod node_num=0 then exit(node div node_num); exit(node div node_num+1); end;procedure Sort(l,r:longint); var i,j,s1,s2:longint; begini:=l; j:=r; s1:=recf[(l+r) div 2]; s2:=right[(l+r) div 2];repeatwhile ((recf[i]<s1)or((recf[i]=s1)and(right[i]<s2))) do inc(i);while ((recf[j]>s1)or((recf[j]=s1)and(right[j]>s2))) do dec(j);if i<=j thenbeginSwap(recf[i],recf[j]); Swap(id[i],id[j]); Swap(left[i],left[j]);Swap(right[i],right[j]); Swap(vall[i],vall[j]); Swap(valr[i],valr[j]);inc(i); dec(j);end;until i>=j;if i<r then Sort(i,r);if j>l then Sort(l,j); end;function Query(l,r,mode:longint):longint; vari:longint;real:array[1..2] of longint; beginQuery:=0; real[1]:=Locate(l); real[2]:=Locate(r);if real[2]-real[1]<=1 then for i:=l to r do inc(Query,block[i,mode])elsebeginfor i:=real[1]+1 to real[2]-1 do inc(Query,intersum[i,mode]);for i:=l to real[1]*node_num do inc(Query,block[i,mode]);for i:=(real[2]-1)*node_num+1 to r do inc(Query,block[i,mode]);end; end;procedure add(x,i:longint); begininc(block[x,1]); inc(intersum[Locate(x),1]);if block[x,1]=1 then begin block[x,2]:=1; inc(intersum[Locate(x),2]); end; end;procedure dim(x,i:longint); begindec(block[x,1]); dec(intersum[Locate(x),1]);if block[x,1]=0 then begin block[x,2]:=0; dec(intersum[Locate(x),2]); end; end;procedure Ready; beginread(n,m); node_num:=trunc(sqrt(n)); block_num:=node_num;if block_num<>sqrt(n) then inc(block_num);for i:=1 to n do read(num[i]);for i:=1 to m do begin id[i]:=i; read(left[i],right[i],vall[i],valr[i]); recf[i]:=Locate(left[i]); end;Sort(1,m); end;beginReady; l:=1; r:=0; sum:=0;for i:=1 to m dobeginwhile r<right[i] do begin inc(r); add(num[r],i); end;while r>right[i] do begin dim(num[r],i); dec(r); end;while l<left[i] do begin dim(num[l],i); inc(l); end;while l>left[i] do begin dec(l); add(num[l],i); end;ans[id[i],1]:=Query(vall[i],valr[i],1); ans[id[i],2]:=Query(vall[i],valr[i],2);end;for i:=1 to m do writeln(ans[i,1],' ',ans[i,2]); end.

轉載于:https://www.cnblogs.com/FibonacciHeap/articles/9785391.html

總結

以上是生活随笔為你收集整理的[AHOI2013]作业的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。