首页 > 代码库 > zzuli1731 矩阵(容斥)

zzuli1731 矩阵(容斥)

1731: 矩阵

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 600  Solved: 106

SubmitStatusWeb Board

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

1 3 4 4 Q 1 1 1 1 Q 1 1 3 2 M 1 1 3 Q 1 1 3 4

Sample Output

2 21 55

HINT

 

 

Source

 

给定一个矩阵,和两种操作Q输出子矩阵的值,M改变一个位置的值,

朴素算法会TLE,采用容斥思想减少for的使用

 

 

 

 

1.1 1.2                      
                         
                         
                         
                                                (a-1,b-1 )                                     (a-1, d)                 
            (a,b)            
                         
                         
                                                   
                               
                         
          (c,b-1)         (c,d)    
                         

不难发现,使用SUM((a,b)->(c,d))=SUM((1,1)->(c,d))-SUM((1,1)->(c,b-1))-SUM((1,1)->(a-1,d))+SUM((1,1)->(a-1,b-1));

所以我们不妨使用一个矩阵dp[i][j]表示SUM((1,1)->(i,j));

这样Q时很方便就能输出结果,M时只要更改下此点往后所有的值即可;

代码:

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
#define CIN(a) scanf("%d",&a)
int e[1005][1005],dp[1005][1005];
int main()
{
int n,m,t,i,j,Q;
char ch;
int t1,t2,t3,t4;
for(i=0;i<=100l;++i) dp[0][i]=0;
cin>>t;
while(t--){int tmp;
scanf("%d%d%d",&n,&m,&Q);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) e[i][j]=i+j;
for(i=1;i<=n;++i){tmp=0;
for(j=1;j<=m;++j){
tmp+=e[i][j];
dp[i][j]=dp[i-1][j]+tmp;
}
}
while(Q--){
scanf(" %c%d%d%d",&ch,&t1,&t2,&t3);
if(ch==‘M‘){
for(i=t1;i<=n;++i)
for(j=t2;j<=m;++j)
dp[i][j]=dp[i][j]-e[t1][t2]+t3;
e[t1][t2]=t3;
}
else if(ch==‘Q‘){CIN(t4);
printf("%d\n",dp[t3][t4]+dp[t1-1][t2-1]-dp[t1-1][t4]-dp[t3][t2-1]);
}

}
}
return 0;
}

 

zzuli1731 矩阵(容斥)