您的位置: 首页  >  IT文章  >  bzoj 2821 分块处理

bzoj 2821 分块处理

分类: IT文章 • 2023-11-17 21:47:54

大题思路就是分块，将n个数分成sqrt(n)个块，然后

处理出一个w数组，w[i,j]代表第i个块到第j个块的答案

那么对于每组询问l,r如果l,r在同一个块中，直接暴力做就行了

如果不在同一个块中，l,r区间中整块的部分可以直接由w数组得到答案

然后多出来的部分暴力处理下出现次数，然后再预处理一个b数组，代表没

个数出现的位置，且每个数都连续，那么我们可以二分的找出在多余部分出现的

每个数在整区间内出现多少次，然后和多余部分出现的累加，判断奇偶更新答案

看了lyd的题解，写的挺好（其实这个题就是他出的。。），然后我写的

pascal，他的C++的代码30s+A了，我就TLE了。。。

话说今儿LYD生日，然后SHY发了个说说祝他生日快乐，是我想多了。。。

/**************************************************************
    Problem: 2821
    User: BLADEVIL
    Language: Pascal
    Result: Time_Limit_Exceed
****************************************************************/
 //By BLADEVIL
{$inline on}
var
    n, t, m                     :longint;
    a, b, c                     :array[0..100010] of longint;
    st, ed, s, e, v, q          :array[0..100010] of longint;
    w                           :array[0..400,0..400] of longint;
 
procedure swap(var a,b:longint);inline;
var
    c                           :longint;
begin
    c:=a; a:=b; b:=c;
end;
     
function calc(k,x,y:longint):longint;inline;
var
    l, r, mid                   :longint;
begin
    if x>y then exit(0);
    l:=st[k]; r:=ed[k];
    while l<r do
    begin
        mid:=(l+r+1)>>1;
        if b[mid]<x then l:=mid else r:=mid-1;
    end;
    if b[l]>=x then dec(l);
    x:=l;
    l:=st[k]; r:=ed[k];
    while l<r do
    begin
        mid:=(l+r+1)>>1;
        if b[mid]>y then r:=mid-1 else l:=mid;//
    end;
    if b[l]>y then dec(l);
    y:=l;
    exit(y-x);
end;
     
procedure main;inline;
var
    i, j, k                     :longint;
    p, tot, l, r                :longint;
    now, cnt                    :longint;
    x, y                        :longint;
     
begin  
    read(n,t,m);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do inc(c[a[i]]);
    tot:=0;
    for i:=1 to t do
    begin
        st[i]:=tot+1;
        inc(tot,c[i]);
        ed[i]:=tot;
    end;
    fillchar(c,sizeof(c),0);
    for i:=1 to n do
    begin
        b[st[a[i]]+c[a[i]]]:=i;
        inc(c[a[i]]);
    end;
    p:=trunc(sqrt(n));
    l:=n div p;
    for i:=1 to p do
    begin
        s[i]:=(i-1)*l+1;
        e[i]:=i*l;
    end;
    if e[p]<n then
    begin
        inc(p);
        s[p]:=e[p-1]+1;
        e[p]:=n;
    end;
    for i:=1 to p do
    begin
        fillchar(c,sizeof(c),0);
        now:=0;
        for j:=i to p do
        begin
            for k:=s[j] to e[j] do
            begin
                inc(c[a[k]]);
                if (c[a[k]]>1) and (c[a[k]] and 1<>0) 
                    then dec(now) else
                if (c[a[k]] and 1)=0 then inc(now);
            end;
            w[i,j]:=now;
        end;
    end;
    now:=0;
    for i:=1 to m do
    begin
        read(x,y);
        x:=(x+now) mod n+1;
        y:=(y+now) mod n+1;
        if x>y then swap(x,y);
        for j:=1 to p do
            if x<=e[j] then
            begin
                l:=j;
                break;
            end;
        for j:=p downto 0 do
            if y>=s[j] then
            begin
                r:=j;
                break;
            end;
        now:=w[l+1,r-1];
        if l=r then
        begin
            for j:=x to y do
                if v[a[j]]<>i then
                begin
                    v[a[j]]:=i;
                    c[a[j]]:=1;
                end else
                begin
                    inc(c[a[j]]);
                    if (c[a[j]] and 1)<>0 then
                        dec(now) else inc(now);
                end;
        end else
        begin
            cnt:=0;
            for j:=x to e[l] do
                if v[a[j]]<>i then
                begin
                    v[a[j]]:=i;
                    c[a[j]]:=1;
                    inc(cnt);
                    q[cnt]:=a[j];
                end else inc(c[a[j]]);
            for j:=s[r] to y do
                if v[a[j]]<>i then
                begin
                    v[a[j]]:=i;
                    c[a[j]]:=1;
                    inc(cnt);
                    q[cnt]:=a[j];
                end else inc(c[a[j]]);
            for j:=1 to cnt  do
            begin
                k:=calc(q[j],s[l+1],e[r-1]);
                if k=0 then
                begin
                    if c[q[j]] and 1=0 then inc(now)
                end else
                if (k and 1<>0) and (c[q[j]] and 1<>0) then inc(now) else
                if (k and 1=0) and (c[q[j]] and 1<>0) then dec(now);
            end;
        end;
        writeln(now);
    end;
     
end;
 
 
begin
    main;
end.

相关推荐