9
17
2013
1

【BZOJ3132】上帝造题的七分钟【二维树状数组】

这道题是对pascal赤果果的鄙视。。。pascal在tyvj上AC了在BZ上WA。要来数据在CENA上AC了再BZ上接着WA。网上抄来PASCAL标程还TM的WA。最后怒了贴个C++结果A了。。。QAQ

二维树状数组的矩形修改和查找。令D[X,Y]表示在矩形(X,Y)(N,M)上加上D[X,Y]。则点(X,Y)的权值就是SIGMA(D(I,J))。然后就瞎搞搞,维护D[X,Y],D[X,Y]*X,D[X,Y]*Y,D[X,Y]*X*Y。然后就可以了。

代码依然PASCAL。我是P党我骄傲

 

program p3132;
    type
        arr=array[0..2050,0..2050] of longint;
    var
        i,j,n,m,k1,k2,k3,k4,k5:longint;
        a,b,c,d:arr;
        ch:char;
    procedure getchar(var k:char);
        begin
            read(k);
            while ((k<'A') or (k>'Z')) and ((k<'a') or (k>'z'))do
                read(k);
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure add(var x:arr;k1,k2,k3:longint);
        var
            i,j:longint;
        begin
            i:=k1; 
            while i<=n do begin
                j:=k2;
                while j<=m do begin
                    x[i,j]:=x[i,j]+k3;
                    j:=j+lowbit(j);
                end;
                i:=i+lowbit(i);
            end;
        end;
    function find(var x:arr;k1,k2:longint):longint;
        var
            i,j,num:longint;
        begin
            i:=k1; num:=0;
            while i>0 do begin
                j:=k2;
                while j>0 do begin
                    num:=num+x[i,j];
                    j:=j-lowbit(j);
                end;
                i:=i-lowbit(i);
            end;
            exit(num);
        end;
    function findtotal(k1,k2:longint):longint;
        begin
            exit((k1+1)*(k2+1)*find(a,k1,k2) - (k1+1)*find(b,k1,k2) - (k2+1)*find(c,k1,k2) + find(d,k1,k2));
        end;
    procedure addtotal(k1,k2,k3,k4,k5:longint); 
        begin
            add(a,k1,k4,k5); add(a,k1,k2+1,-k5); add(a,k3+1,k4,-k5); add(a,k3+1,k2+1,k5);
            add(b,k1,k4,k5*k4); add(b,k1,k2+1,-k5*(k2+1)); add(b,k3+1,k4,-k5*k4); add(b,k3+1,k2+1,k5*(k2+1));
            add(c,k1,k4,k5*k1); add(c,k1,k2+1,-k5*k1); add(c,k3+1,k4,-k5*(k3+1)); add(c,k3+1,k2+1,k5*(k3+1));
            add(d,k1,k4,k5*k1*k4); add(d,k1,k2+1,-k5*k1*(k2+1)); add(d,k3+1,k4,-k5*(k3+1)*k4); add(d,k3+1,k2+1,k5*(k3+1)*(k2+1));
        end;
    begin
        getchar(ch);
        readln(n,m);
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        while not eof do begin
            getchar(ch);
            if ch='L' then begin
                readln(k1,k2,k3,k4,k5);
                addtotal(k1,k4,k3,k2,k5);
            end else if ch='k' then begin
                readln(k1,k2,k3,k4);
                writeln(findtotal(k3,k4)+findtotal(k1-1,k2-1)-findtotal(k1-1,k4)-findtotal(k3,k2-1));
            end;
        end;
    end.
Category: 数据结构 | Tags: | Read Count: 3216
Avatar_small
Maya Gatty 说:
2019年4月01日 20:05

In the blog the first sticker is looking for something and also looking really worried that is the reason of headache of him. Second about the part of the blog with the flowing of the arms as they are best essays review to be got when they will happier.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com