「RiOI-03」网格

Luogu

IDLGP9917

Time1000ms

Memory512MB

DifficultyP6

树状数组洛谷原创O2优化洛谷月赛分类讨论

**请仔细阅读本题数据范围。** 给定一个 $n\times n$ 的正方形网格，一共有 $n$ 行，$n$ 列，初始时所有网格均为红色。有 $n$ 组询问，每次询问会把一整行或一整列的颜色全部染成红色或白色，每次询问后输出所有红色网格的周长，而且询问之间不独立。 ## Input 第一行为一个正整数 $n$；接下来的 $n$ 行，每行三个正整数 $w,y,x$。$w$ 表示颜色，$w=1$ 表示染成红色，$w=0$ 表示染成白色。$y$ 表示行或列，$y=1$ 表示把第 $x$ 行全部染色，$y=0$ 表示把第 $x$ 列全部染色。 ## Output 一共有 $n$ 行，每行一个整数，表示每次修改后的红色部分周长。 [samples] ## Background 2022 年某次集训讲课，课件中出现了一道以 MLE 真名首字母严格顺序作为输入变量的题目。MLE 就想在自己的题目里用 [vectorwyx](https://www.luogu.com.cn/user/238408) 的首字母当输入变量，于是就有了这道题。可惜如今 [vectorwyx](https://www.luogu.com.cn/user/238408) 已经退役了，人生有梦，各自精彩。 ## Note ### 样例解释 [样例图片解释](https://www.luogu.com.cn/paste/rvrhouei) ### 数据范围对于 $100\%$ 的数据，$3\leq n \leq 10^6 $，$1<x<n$。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{\textsf{\#}} & \bm{{n\le}} & \textbf{\textsf{特殊性质}} & \textbf{\textsf{\#}} & \bm{{n\le}} & \textbf{\textsf{特殊性质}}\cr\hline 1 & 5 & - & 11 & 10^5 & - \cr\hline 2 & 100 & - & 12 & 10^5 & - \cr\hline 3 & 100 & - & 13 & 10^5 & - \cr\hline 4 & 2000 & \textbf{A} & 14 & 10^5 & - \cr\hline 5 & 2000 & \textbf{B} & 15 & 10^6 & - \cr\hline 6 & 2000 & - & 16 & 10^6 & - \cr\hline 7 & 10^5 & \textbf{AB} & 17 & 10^6 & - \cr\hline 8 & 10^5 & \textbf{B} & 18 & 10^6 & - \cr\hline 9 & 10^5 & \textbf{A} & 19 & 10^6 & - \cr\hline 10 & 10^5 & - & 20 & 10^6 & - \cr\hline \end{array} $$ - 特殊性质 $\bf A$：保证 $w=0$。 - 特殊性质 $\bf B$：保证 $y=0$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「RiOI-03」网格",
    "description": {
      "content": "**请仔细阅读本题数据范围。** 给定一个 $n\\times n$ 的正方形网格，一共有 $n$ 行，$n$ 列，初始时所有网格均为红色。有 $n$ 组询问，每次询问会把一整行或一整列的颜色全部染成红色或白色，每次询问后输出所有红色网格的周长，而且询问之间不独立。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9917"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**请仔细阅读本题数据范围。**\n\n给定一个 $n\\times n$ 的正方形网格，一共有 $n$ 行，$n$ 列，初始时所有网格均为红色。有 $n$ 组询问，每次询问会把一整行或一整列的颜色全部染成红色或白色，每次询问后输出所有红色网格的周长，而且询问之间不独立。\n\n## Input\n\n第一行为一个正整数 $n$；\n\n接下来的 $n$ 行，每行三个正整数 $w,y,x$。$w$ 表示颜色，$w=...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments