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