#BZOJ2874. 训练士兵
-
ID: 1354
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
训练士兵
No submission language available for this problem.
题目描述
Ryz<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">正在着手于训练一批精锐士兵。</span><o:p></o:p>
Ryz<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">手下有</span>n*m<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">个士兵，排成一个</span>n<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">行</span>m<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">列的方阵。在一天中，</span>ryz<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">会对士兵下达一些命令，每个命令作用于一个小方阵的所有士兵，并且会增加他们的疲劳值。现在</span>ryz<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">想知道，在一整天训练中，某些小方阵中的士兵的疲劳值总和是多少。</span><o:p></o:p>
<span lang="EN-US" style="font-size:12.0pt;mso-bidi-font-size:
10.0pt"><o:p> </o:p></span>
输入格式
第一行有3个整数n,m,k,q。分别表示方阵的行数、列数、指令数和询问数。<o:p></o:p>
接下来k行，每行5个整数x1,x2,y1,y2,s，描述一个指令，表示这条指令对所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵产生了s的疲劳值。<o:p></o:p>
(1<=x1<=x2<=n，1<=y1<=y2<=m，0<=s<=1000)<o:p></o:p>
接下来q行，每行2个整数x,y(x,y<=10^9)，描述一个询问，询问是被加密的。一个询问的密码是上一个询问的答案(记为c)，第一个询问的密码是0。询问参数的计算方式如下：<o:p></o:p>
x1=c % n+1,x2=(c+x) % n+1，如果x1>x2则交换x1和x2<o:p></o:p>
y1=c % m+1,y2=(c+y) % m +1，如果y1>y2则交换y1和y2<o:p></o:p>
询问所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵的疲劳值总和。<o:p></o:p>
保证答案<2^64。<o:p></o:p>
<o:p> </o:p>
输出格式
对于每个询问，输出一行答案。<o:p></o:p>
<o:p> </o:p>
输入样例1
4 5 3 3
1 3 2 2 7
2 4 2 3 5
1 4 4 5 6
1 2
0 3
2 2
输出样例1
24
12
46
第一次询问的是左上角坐标为(1,1),右下角坐标为(2,3)的这个矩形
第二次询问的是左上角坐标为(1,3),右下角坐标为(1,5)的这个矩形
第三次询问的是左上角坐标为(1,3)，右下角坐标为(3,5)这个矩形
输入样例2
5 5 5 5
1 1 1 3 242
1 4 4 5 83
3 5 3 3 221
2 2 1 3 254
5 5 2 2 105
0 1
0 4
2 1
1 3
0 1
输出样例2
484
0
992
442
304
数据范围与约定
<span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;<br />
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";mso-font-kerning:1.0pt;
mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">对于</span><span lang="EN-US" style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:"Times New Roman";
mso-fareast-font-family:宋体;mso-font-kerning:1.0pt;mso-ansi-language:EN-US;
mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">100%</span><span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:
"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:
ZH-CN;mso-bidi-language:AR-SA">的数据</span><span lang="EN-US" style="font-size:
12.0pt;mso-bidi-font-size:10.0pt;font-family:"Times New Roman";mso-fareast-font-family:
宋体;mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"> n,m<=10^8,k<=40000,q<=100000</span><span style="font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:
"Times New Roman";mso-font-kerning:1.0pt;mso-ansi-language:EN-US;mso-fareast-language:
ZH-CN;mso-bidi-language:AR-SA">；</span>