题解 P4396 【[AHOI2013]作业】

arfa · 2018-10-07 07:44:31 · 题解

先知道这道题目的所求

• 求出一个 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); // 增加一个数
begin
    inc(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); // 减少一个数字
begin
    dec(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
var
    block_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;
begin
    i:=l; j:=r; s1:=recf[(l+r) div 2]; s2:=right[(l+r) div 2];
    repeat
        while ((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 then
        begin
            Swap(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;
var
    i:longint;
    real:array[1..2] of longint;
begin
    Query:=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])
    else
    begin
        for 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);
begin
    inc(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);
begin
    dec(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;
begin
    read(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;

begin
    Ready; l:=1; r:=0; sum:=0;
    for i:=1 to m do
    begin
        while 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.