• [D] Chihuo IV - Evidence

  • 时间限制: 3000 ms 内存限制: 65535 K
  • 问题描述
  • After Tianyi ate some food, she decided to bury the evidence she had eaten. Because she's afraid that Zhengling will know it.
    First, the square is a big hole that the acreage is N * N. At each step, Tianyi will choose a coordinate to bury.
    Then Tianyi will ask you that during step X to step Y, the sum of maximum independent holes area.

    For example:
    The big hole is 3 * 3. Step 1 buries (2, 2), so the maximum independent hole area is 8. Step 2 buries (2, 1), so the maximum independent hole area is 7. Step 3 buries (2, 3), so the maximum independent hole area is 3.
    That is, from step 1 to step 3, the sum of independent hole is (8 + 7 + 3) = 18.


  • 输入
  • This problem contains several cases.
    The first line of each case is an integer N (0 < N <= 500), indicates the length of side.
    Then follows N * N lines, each line is a coordinate. From (1, 1) to (N, N). You can assume that one coordinate will at most appear once.
    Next line follows an integer Q (0 < Q <= 10000), indicates the count of queries.
    Next Q lines indicate Q queries.
  • 输出
  • For each query, you should output the sum of independent holes.
  • 样例输入
  • 3
    1 1
    1 3
    2 2
    2 3
    3 2
    1 2
    3 3
    2 1
    3 1
    1
    1 1
    
  • 样例输出
  • 8
    
  • 提示
  • 来源
  • XadillaX
  • 操作

显示春菜