-7

有一个魔术板。魔术板有 N*N 个单元：N 行和 N 列。每个单元格包含一个整数，最初为 0。让行和列从 1 到 N 编号。

有2种操作可以应用于魔术板：

•RowSet ix：表示经过此操作后，第i 行单元格中的所有整数都已更改为x。

•ColSet ix：表示在此操作后第i 列单元格中的所有整数都已更改为x。

您的朋友有时对某行或某列上的整数 0 的总数感兴趣：

•RowQuery i：表示您应该回答第i 行0 的总数。

•ColQuery i：表示您应该回答第i 列0 的总数。

输入

第一行输入包含 2 个空格分隔的整数 N 和 Q。它们表示魔术板的大小，以及来自朋友的操作和查询的总数。

然后接下来的 Q 行中的每一行都包含上述格式的操作或查询。

输出

对于每个查询，输出查询的答案。

约束

1≤N，Q≤500000（5*105）

1≤i≤N

x ∈ {0, 1}（即 x = 0 或 1）

样本输入：

3 6

行查询 1

集合 1 1

行查询 1

ColQuery 1

行集 1 0

ColQuery 1

输出：3

2

0

1

怎么办？时间限制为 0.6 秒，因此在 2D 数组上标记操作的简单算法将不起作用。

4

1 回答 1

3

如果你想不出一个好的算法，试试这个技术：

  1. 使用铅笔和方格纸运行一个示例。
  2. 再次运行一个示例，这次记下您执行的每个详细步骤。
  3. 使用您的步骤再次运行示例。根据需要进行调整。
  4. 将您的步骤转换为代码。

使用这种技术，您可以提出更合适的问题在 Stackoverflow 上进行搜索，例如“如何实现一个正方形的内存/矩阵区域？”

或者“我如何使用调试器？”

或者“这是重现我的问题的最小程序......，我做错了什么？”

编辑1：（提高我的SO声誉）

从需求来看，您至少需要两个功能：将行设置为给定值或将列设置为给定值。

让我们从像 4x4 矩阵这样的小东西开始。并使用命令： Set Row 1 0 // 将第 1 行设置为全零。请记住，C++ 索引从 0 到 N-1 而不是 1 到 N 的要求是，所以我们必须从我们的行号中减去一个。让我们使用符号：board[row][column]表示板上的一个单元格。用手：

  board[0][0] = 0;
  board[0][1] = 0; // Note the incrementing column numbers.
  board[0][2] = 0;
  board[0][3] = 0; // Note the last column index is 3 not 4.

看上面的代码，我们可以注意到一个模式，即列索引每次都在变化，1。所以我们可以把它放到一个循环中：

  Set column to zero.
  While column is less than 4 do:
      board[0][column] = 0;
      column = column + 1;
      end-while

下一步是将其转换为一些代码： 

  unsigned int column;
  unsigned int board[4][4];
  for (column = 0; column < 4; ++column)
  {
       board[0][column] = 0;
  }

由于该Set Row命令允许可变行索引和可变行值，我们制作这些变量并将它们插入到我们的代码中： 

unsigned int row = 0;
unsigned int value = 0;
unsigned int column;
unsigned int board[4][4];
for (column = 1; column < 4; ++column)
{
    board[row][column] = value;
}

我们可以通过提供函数签名将其变成一个独立的函数： 

void Set_Row(unsigned int& array[4][4],
             unsigned int  row,
             unsigned int  value)
{
   // Insert above code fragment here.
}

接下来，为其他命令创建函数。
创建一个main函数来读取命令。
运行程序，注意问题出在哪里，例如能够在运行时声明任意大小的矩阵。
添加代码以解决问题。
重复。

于 2013-02-07T00:06:51.383 回答