1731: 矩陣
Time Limit: 3 Sec
Memory Limit: 128 MB
Submit: 546
Solved: 86
Submit
Status
Web Board
Description
Input
Output
Sample Input
13 4 4Q 1 1 1 1Q 1 1 3 2M 1 1 3Q 1 1 3 4
Sample Output
22155
HINT
-----(x,y)
1.1 | 1.2 |
(a-1,b-1 ) | (a-1, d) |
(a,b) | |
(c,b-1) | (c,d) |
容斥原理:
求(a,b)---(c,d)矩陣的和
就等于(1,1)---(c,d) 減去 (1,1)--------( c,b-1 ) 減去 ( 1,1 )------( a-1,d ) 加上 ( 1,1 )---( a-1,b-1 )
#include<cstdio>
#include<cstring>
int shu[1010][1010],zhen[1010][1010];
int main()
{
int t,n,m,q;scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&q);
memset(shu,0,sizeof(shu));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
shu[i][j]=i+j;
memset(zhen,0,sizeof(zhen));
for (int i=1;i<=n;i++)
{
int ss=0;
for (int j=1;j<=m;j++)
{
ss+=shu[i][j];
zhen[i][j]=zhen[i-1][j]+ss;
}
}
char ch;
while (q--)
{
getchar();
scanf("%c",&ch);
if (ch=='Q')
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",zhen[c][d]-zhen[c][b-1]-zhen[a-1][d]+zhen[a-1][b-1]);
}
else
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
for (int i=a;i<=n;i++)
for (int j=b;j<=m;j++)
zhen[i][j]+=c-shu[a][b];
shu[a][b]=c;
}
}
}
return 0;
}