D. 网格图差异问题

    传统题 文件IO:diff 500ms 256MiB

网格图差异问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

看起来你很喜欢网格图。

题目描述

  • 给出一个 nnnn 列的网格图,每个格子被染成黑色或白色。
  • 初始情况下,若 i+ji + j 为奇数则 (i,j)(i,j) 被染成黑色,否则 (i,j)(i,j) 被染成白色。
  • 现在有 kk 个格子的颜色被改变了,即如果是黑色则变为白色,如果是白色则变为黑色。
  • 你需要找出一个子矩形,使得矩形中黑色格子和白色格子数量差的绝对值最大,并输出这个值。
  • 你可以通过阅读样例解释更好地理解题意。

输入格式

从文件 diff.in 中读入。

  • 第一行两个数 n,kn, k
  • 接下来 kk 行,每行两个数 x,yx, y,表示一个颜色被改变的格子,保证每个格子至多出现一次。

输出格式

输出到文件 diff.out 中。

  • 一行一个整数表示答案。

样例输入输出

3 1  
1 1
3 4  
1 2  
2 1  
2 3  
3 2  
3 4  
1 1  
1 3  
3 1  
3 3
2  
9  
7

样例解释

【样例解释 1】 (1,1) 原本为白色,现在被染成了黑色,以 (1,1) 为左上角,(2,2) 为右下角的矩形中共有 3 黑 1 白,答案为 2。

【样例解释 2】 所有 9 个格子被染成了白色,答案为 9。

【样例解释 3】 除了 (2,2) 的 8 个格子被染成了黑色,答案为 7。

数据范围

  • 1n1091 \leq n\leq 10^9
  • 1k501\leq k\leq 50

测试点分布

  • 本题不设子任务捆绑
  • 保证被改变颜色的点的位置在整个网格图中均匀随机
  • 本题所有测试点等分
  • 数据强度具有一定梯度
  • 请留意本题不同寻常的时间限制
测试点编号 限制
1~20 k=1,n=5k=1,n=5
21~100 N/A

大样例下载

  • 编号为 1 的大样例满足测试点 1~20 的限制
  • 编号为 2 的大样例满足测试点 21~100 的限制

24KOI 2025 体验赛 No.4

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-6-22 13:00
结束于
2025-6-22 16:30
持续时间
3.5 小时
主持人
参赛人数
33