365bet体育在线您加入之后,很多人表示自己得到了前所未有的乐趣。
当前位置: > 365bet体育在线 >

2018 ICPC南京站网绕赛 The writing on the wall(无赖栈追

发布时间: 2018-10-14 05:41  |  来源: 未知  |  作者: admin
Feeling hungry, a cute hamster decides to order some take-away food (like fried chicken for only?3030?Yuan). However, his owner CXY thinks that take-away food is unhealthy and expensive. So she demands her hamster to fulfill a mission befor

  Feeling hungry, a cute hamster decides to order some take-away food (like fried chicken for only?3030?Yuan).

  However, his owner CXY thinks that take-away food is unhealthy and expensive. So she demands her hamster to fulfill a mission before ordering the take-away food. Then she brings the hamster to a wall.

  The wall is covered by square ceramic tiles, which can be regarded as a?n * mn?m?grid. CXY wants her hamster to calculate the number of rectangles composed of these tiles.

  For example, the following?3 * 33?3?wall contains?3636?rectangles:

  Such problem is quite easy for little hamster to solve, and he quickly manages to get the answer.

  Seeing this, the evil girl CXY picks up a brush and paint some tiles into black, claiming that only those rectangles which don't contain any black tiles are valid and the poor hamster should only calculate the number of the valid rectangles. Now the hamster feels the problem is too difficult for him to solve, so he decides to turn to your help. Please help this little hamster solve the problem so that he can eoy his favorite fried chicken.

  There are multiple test cases in the input data.

  The first line contains a integer?TT?: number of test cases.?T \le 5T≤5.

  For each test case, the first line contains?33?integers?n , m , kn,m,k?, denoting that the wall is a?n \times mn×m?grid, and the number of the black tiles is?kk.

  For the next?kk?lines, each line contains?22?integers:?x\ yx?y?,denoting a black tile is on the?xx-th row and?yy-th column. It's guaranteed that all the positions of the black tiles are distinct.

  For all the test cases,

  1 \le n \le 10^5,1\le m \le 1001≤n≤105,1≤m≤100,

  0 \le k \le 10^5 , 1 \le x \le n, 1 \le y \le m0≤k≤105,1≤x≤n,1≤y≤m.

  It's guaranteed that at most?22?test cases satisfy that?n \ge 20000n≥20000.

  For each test case, print "Case #xx:?ansans" (without quotes) in a single line, where?xx?is the test case number and?ansans?is the answer for this test case.

  The second test case looks as follows:

  样例输入骈制

  2

  3 3 0

  3 3 1

  2 2

  样例输入骈制

  Case #1: 36

  Case #2: 20

  文思:把白色看成1,黑色看成0,。题意坚硬是寻求寻求1儿子矩阵的数。

  比值先 n^3 的算法文思:

  矩阵:

  1 1 1 1

  0? 1 1 1

  0? 0? 1 1

  0? 0? 0? 1

  考虑每个点对恢复案的贡献,先看(1,1)位置,值为1,此雕刻它不得不结合1个矩阵,对恢复案的贡献是1,接着看(1,2),它却以和孤立贡献1个儿子矩阵,同时也却以和前面(1,1),团结贡献1,因此它的尽贡献先定为2(之因此此雕刻么说,是鉴于当今我们条考虑行的影响,关于列的影响,壹会会剖析)。接着看(1,3),它却以贡献3个矩阵(己己己,和2,和1,2).同理剖析(1,4).