#PQJ85x10791. QOJ 85_10791

    ID: 3048 传统题 10000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2012线段树

QOJ 85_10791

IOI2012 中国队选拔赛暨精英赛 第二试 统计学家 统计学家 【问题描述】 给定一个NM 的整数矩阵{A[i, j]}(1 ≤ i ≤ N, 1≤ j ≤ M)。请回答K 个询问, 其中第i 个询问要求统计满足下述条件的二维逆序对 (x1, y1, x2, y2)的个数: ui,1 ≤ x1 ≤ x2 ≤ ui,2 且 vi,1 ≤ y1 ≤ y2 ≤ vi,2; 且 A[x1, y1] > A[x2, y2]。 【输入格式】 本题为提交答案试题,输入文件rev1.in~rev10.in 已经在选手目录下。 输入文件rev.in 的第一行依次包含三个正整数N,M 和K。接下来N 行, 每行M 个数给出整数矩阵A,其中第i 行第j 个数为A[i, j]。接下来K 行,每行 四个整数给出所有的询问,其中第i 行依次为ui,1,vi,1,ui,2,vi,2。 【输出格式】 输出文件rev*.out 的包含K 行,其中第i 行为一个整数,对应的第i 个询问 的答案,即满足相应条件的二维逆序对个数。 【样例输入】 3 5 3 1 2 3 4 5 9 9 9 9 9 1 4 3 5 2 1 1 2 5 3 1 3 5 2 1 3 5 【样例输出】 0 4 19 【评分标准】 对于每个测试点,如果你有输出,且输出结果与标准输出完全一致,则该测 试点得10 分,否则该测试点得0 分。 【特别提示】 请妥善保存输入文件*.in 和你的输出*.out,及时备份,以免误删。 第5 页 共5 页