Problem B

發(fā)布時間: 2017年6月28日 10:06?? 最后更新: 2017年6月28日 16:35?? 時間限制: 2000ms?? 內(nèi)存限制: 32M

描述

給定一個n×m的矩形, 其中第i行第j列的值為ai,j

給出q個操作, 操作有兩種

對于形如1?x1?y1?x2?y2?z?的操作, 將(x1,y1)-(x2,y2)這段矩形區(qū)域的所有元素加上z, 滿足1≤x1≤x2≤n,?1≤y1≤y2≤m,?1≤z≤105

對于形如2?x?y的操作, 輸出ax,y, 滿足1≤x≤n,?1≤y≤m

998≤n≤1000,?998≤m≤1000,?9×104≤q≤105,?1≤ai,j≤105

輸入

第一行三個整數(shù)n,?m,?q, 意義如上所述。
接下來n行, 每行m個整數(shù), 表示序列a。
再接下來q行, 每行第一個數(shù)為opt, 如果opt=1, 則后面緊跟五個數(shù), 意義如上所述; 如果opt=2, 則后面緊跟兩個數(shù), 意義如上所述。

輸出

對于所有操作2, 輸出答案, 一行一個。

樣例輸入1?復制 3 4 3 3 1 4 1 5 9 2 6 5 3 5 8 2 2 2 1 1 1 3 4 6 2 2 2 樣例輸出1 9 15

題解：

這道題目給出的操作是對要做區(qū)間修改，端點查詢。我們可以仿照《數(shù)據(jù)結(jié)構(gòu)訓練1》的思路，構(gòu)造出一個序列b，然后單點查詢變成了對序列b進行求和，區(qū)間修改變成了

對序列b進行的單點修改。

經(jīng)過嘗試，我們定義b[i][j] = a[i][j]+a[i-1][j-1]-a[i][j-1]-a[i-1][j]

這樣的話 sum(b[i][j])就等于a[i][j]

而我們對于區(qū)間x1,y1,x2,y2進行修改(加上在z)就相當于

在點b[x1][y1]處加上z

在b[x1][y2+1]處減去z

在b[x2+1][y1]處減去z

在b[x2+1][y2+1]處加上z

做以上4步操作。

這樣的話求和就很簡單了，現(xiàn)在可以用兩種方法來實現(xiàn)求和

比較簡單的一種想法是用二維樹狀數(shù)組來維護，這里就不多說了。

還有一種思路就是用分塊的方法，在O(q(sqrt n*m))的復雜度內(nèi)完成

由于二維矩陣在分塊上比較復雜。

我們轉(zhuǎn)向?qū)υ儐栠M行分塊。

每塊地大小是s = sqrt(n*m)

每經(jīng)過s個詢問，我們都要對b數(shù)組和sum數(shù)組進行重構(gòu)。

時間復雜度就是O(q(sqrt n*m))

代碼：

#include <cstdio> #include <cmath> const int MAX = 1007; typedef long long LL; LL cx1[100007]; LL cy1[100007]; LL cx2[100007]; LL cy2[100007]; LL cv[100007]; LL arr[MAX][MAX]; LL brr[MAX][MAX]; LL sum2[MAX][MAX]; LL tot = 0; LL las = 0; LL n,m,q; LL s; void cg(LL x1,LL y1,LL x2,LL y2,LL val){cx1[tot] = x1;cy1[tot] = y1;cx2[tot] = x2;cy2[tot] = y2;cv[tot] = val;tot ++;if(las + s == tot ){//重構(gòu) for(LL i = las;i < tot;i++){brr[cx1[i]][cy1[i]] += cv[i];brr[cx2[i]+1][cy2[i]+1] += cv[i];brr[cx1[i]][cy2[i]+1] -= cv[i];brr[cx2[i]+1][cy1[i]] -= cv[i];}las = tot;for(LL i = 1;i <= n;i++){for(LL j = 1;j <= m;j++){sum2[i][j] = sum2[i][j-1] + sum2[i-1][j] - sum2[i-1][j-1] + brr[i][j];}} } } LL sums(LL x,LL y){LL res = sum2[x][y];for(LL i = las;i < tot;i++){if(cx1[i] <= x && x <= cx2[i] && cy1[i] <= y && y <= cy2[i]){res += cv[i];}}return res; }int main(){//freopen("2.in","r",stdin);//freopen("2.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&q);s = (LL)sqrt(n*m);for(LL i = 1;i <= n;i++){for(LL j = 1;j <= m;j++){scanf("%lld",&arr[i][j]);}}for(LL i = 1;i <= n;i++){for(LL j = 1;j <= m;j++){brr[i][j] = arr[i][j] + arr[i-1][j-1] - arr[i][j-1] - arr[i-1][j];}}for(LL i = 1;i <= n;i++){for(LL j = 1;j <= m;j++){sum2[i][j] = sum2[i][j-1] + sum2[i-1][j] - sum2[i-1][j-1] + brr[i][j];}} while(q--){LL opt;scanf("%lld",&opt);if(opt == 2){//查詢 LL a,b;scanf("%lld%lld",&a,&b);printf("%lld\n",sums(a,b));sums(a,b);}else if(opt == 1){LL a,b,c,d,z;scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&z);cg(a,b,c,d,z);}}return 0;} /* 2 2 4 1 1 1 1 1 1 1 1 1 10 1 2 2 2 2 10 2 1 1 2 2 2 */

總結(jié)

以上是生活随笔為你收集整理的2017西安交大ACM小学期数据结构 [分块、二维矩阵]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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