题解报告——上帝造题的七分钟

传送门

题目背景

裸体就意味着身体。

题目描述

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了

输入输出格式

输入格式：

输入数据的第一行为X n m，代表矩阵大小为

L a b c d delta —— 代表将
k a b c d —— 代表求

请注意，

输出格式：

针对每个k操作，在单独的一行输出答案。

输入输出样例

输入样例#1： 复制

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

输出样例#1： 复制

说明

对于10%的数据，

$【思路分析】$

$一道描述很清奇的题目，而且居然是黑题！！！？？？机房有人选这道题做难题选讲，结果题目一给就基本会做了（至少会口胡）。如果上一道是很水的LCT的话，那么这道题就是更更水的二维区间修改，显然对于二维区间修改我们可以想到的算法有：二维树状数组，CDQ分治，KD—Tree。（然而感觉这辈子都不会写KD—Tree了）$

$鉴于这道题的数据范围很小，我们就选择码量较小的二维树状数组（可能不会少很多，而且应该是最慢的）。$

$不会二维树状数组的读者可以看这篇博客，感觉讲得蛮不错。$

$【代码实现】$

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cctype>
 4 #define lowbit(x) x&(-x)
 5 using namespace std;
 6 const int maxn=2050;
 7 int t[maxn][maxn][4],n,m,a,b,c,d,w;
 8 inline int read()
 9 {
10     char c;
11     int f,x=0;
12     while(!isdigit(c=getchar())&&c!='-'); c=='-'?(f=-1,x=0):(f=1,x=c-'0');
13     while(isdigit(c=getchar())) x=x*10+c-'0';
14     return x*f;
15 }
16 void add(int x,int y,int pp,int ww)
17 {
18     for(int i=x;i<=n;i+=lowbit(i))
19     for(int j=y;j<=m;j+=lowbit(j))
20     t[i][j][pp]+=ww;
21 }
22 int ask(int x,int y,int pp)
23 {
24     int ans=0;
25     for(int i=x;i;i-=lowbit(i))
26     for(int j=y;j;j-=lowbit(j))
27     ans+=t[i][j][pp];
28     return ans;
29 }
30 void ADD(int x,int y,int ww)
31 {
32     add(x,y,0,ww);
33     add(x,y,1,ww*x);
34     add(x,y,2,ww*y);
35     add(x,y,3,ww*x*y);
36 }
37 int ASK(int x,int y)
38 {
39     int ans=ask(x,y,0)*(x*y+x+y+1)-ask(x,y,1)*(y+1)-ask(x,y,2)*(x+1)+ask(x,y,3);
40     return ans;
41 }
42 int main()
43 {
44     char ch[3];
45     scanf("%s%d%d",ch,&n,&m);
46     while(~scanf("%s",ch))
47     {
48         a=read(),b=read(),c=read(),d=read();
49         if(ch[0]=='L')
50         {
51             w=read();
52             ADD(a,b,w),ADD(a,d+1,-w),ADD(c+1,b,-w),ADD(c+1,d+1,w);
53         }
54         if(ch[0]=='k') printf("%d
",ASK(a-1,b-1)+ASK(c,d)-ASK(a-1,d)-ASK(c,b-1));
55     }
56     return 0;
57 }