jiry_2's Blog

这道题是对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.