6874: BZOJ2874:训练士兵
Memory Limit:512 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Ryz正在着手于训练一批精锐士兵。
Ryz手下有n*m个士兵,排成一个n行m列的方阵。在一天中,ryz会对士兵下达一些命令,每个命令作用于一个小方阵的所有士兵,并且会增加他们的疲劳值。现在ryz想知道,在一整天训练中,某些小方阵中的士兵的疲劳值总和是多少。
输入格式
第一行有3个整数n,m,k,q。分别表示方阵的行数、列数、指令数和询问数。
接下来k行,每行5个整数x1,x2,y1,y2,s,描述一个指令,表示这条指令对所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵产生了s的疲劳值。
(1<=x1<=x2<=n,1<=y1<=y2<=m,0<=s<=1000)
接下来q行,每行2个整数x,y(x,y<=10^9),描述一个询问,询问是被加密的。一个询问的密码是上一个询问的答案(记为c),第一个询问的密码是0。询问参数的计算方式如下:
x1=c % n+1,x2=(c+x) % n+1,如果x1>x2则交换x1和x2
y1=c % m+1,y2=(c+y) % m +1,如果y1>y2则交换y1和y2
询问所有坐标(x,y)满足x1<=x<=x2且y1<=y<=y2的士兵的疲劳值总和。
保证答案<2^64。
输出格式
对于每个询问,输出一行答案。
样例输入
输入样例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
提示
对于100%的数据 n,m<=10^8,k<=40000,q<=100000;
题目来源
By Ryz