文章目錄

• 題目描述
• 解析
• 代碼
• thanks for reading！

題目描述

解析

差點活活惡心死
搬磚題
（其實細節(jié)沒有那么多，還是代碼能力太差）

利用矩陣的二維差分
加上樹狀數(shù)組搞一搞
就完事了（我實在不想再寫了 ）

洛谷的雙倍經(jīng)驗沒有那么好水
MLE！
這題洛谷的空間限制非常苛刻
幾乎沒有多余的空間

以后要增強對空間復雜度的敏感性

代碼

（看我的print就能看出我調(diào)了多久）

#include<bits/stdc++.h> using namespace std; const int N=2050; #define ll long long int d[N][N]; ll id[N][N],jd[N][N],ijd[N][N]; int n,m;void add_d(int x,int y,ll v){ // printf("\nx=%d y=%d v=%lld\n",x,y,v);for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j){d[i][j]+=v; // printf("x=%d y=%d\n",i,j);}} } ll ask_d(int x,int y){ // printf("\nask:\nx=%d y=%d\n",x,y);ll ans=0;for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){ans+=d[i][j];} }return ans; } void add_id(int x,int y,ll v){v*=x; // printf("\nx=%d y=%d v=%lld\n",x,y,v);for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j) id[i][j]+=v;//printf("x=%d y=%d\n",i,j);} } ll ask_id(int x,int y){ll ans=0; // printf("ask:x=%d y=%d\n------------\n",x,y);for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){ans+=id[i][j]; // printf("x=%d y=%d\n",i,j);} }return ans; } void add_jd(int x,int y,ll v){v*=y;for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j) jd[i][j]+=v;} } ll ask_jd(int x,int y){ll ans=0;for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){ans+=jd[i][j];} }return ans; } void add_ijd(int x,int y,ll v){v*=x*y;for(int i=x;i<=n;i+=i&-i){for(int j=y;j<=m;j+=j&-j) ijd[i][j]+=v;} } ll ask_ijd(int x,int y){ll ans=0;for(int i=x;i;i-=i&-i){for(int j=y;j;j-=j&-j){ans+=ijd[i][j];} }return ans; }void add(int x1,int y1,int x2,int y2,ll v){add_d(x1,y1,v);add_d(x2+1,y2+1,v);add_d(x1,y2+1,-v);add_d(x2+1,y1,-v);add_id(x1,y1,v);add_id(x2+1,y2+1,v);add_id(x1,y2+1,-v);add_id(x2+1,y1,-v);add_jd(x1,y1,v);add_jd(x2+1,y2+1,v);add_jd(x1,y2+1,-v);add_jd(x2+1,y1,-v);add_ijd(x1,y1,v);add_ijd(x2+1,y2+1,v);add_ijd(x1,y2+1,-v);add_ijd(x2+1,y1,-v); } ll ask(int x,int y){ // printf("ok%lld\n",d[2][1]); // n--;m--;ll res=(x*y+x+y+1)*ask_d(x,y)+ask_ijd(x,y)-(y+1)*ask_id(x,y)-(x+1)*ask_jd(x,y); // printf("x=%d y=%d d=%lld id=%lld jd=%lld ijd=%lld ans=%lld\n",x,y, // ask_d(x,y),ask_id(x,y),ask_jd(x,y),ask_ijd(x,y),res); // cout<<res<<endl; // n++;m++;return res; } int main(){ // printf("%d",sizeof(d)/1024/1024);char flag;scanf("%c%d%d",&flag,&n,&m); // add_id(1,1,2);add_id(2,2,1); // printf("%lld\n",ask_id(3,3));int a,b,c,e,w;while(scanf(" %c",&flag)!=EOF){if(flag=='L'){scanf("%d%d%d%d%d",&a,&b,&c,&e,&w);add(a,b,c,e,w); // printf("okk:%lld\n",ask_d(1,1));}else{scanf("%d%d%d%d",&a,&b,&c,&e); // printf("okk:%lld\n",ask_d(1,1));printf("%lld\n",ask(c,e)+ask(a-1,b-1)-ask(a-1,e)-ask(c,b-1));} // printf("------------opp:%lld\n",ask_id(3,3));} return 0; } /**/

thanks for reading！

總結(jié)

以上是生活随笔為你收集整理的上帝造题的七分钟（ybtoj-树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。