[Ynoi2002] Optimal Ordered Problem Solver

Luogu

IDLGP9061

Time4000ms

Memory512MB

DifficultyP7

2002O2优化Ynoi

给定 $n$ 个点 $(x_i,y_i)_{i=1}^n$，你需要按顺序处理 $m$ 次操作。每次操作给出 $o,x,y,X,Y$， - 首先进行修改： - 若 $o=1$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $y_i$ 修改为 $y$； - 若 $o=2$ 则将满足 $x_i\le x,\;y_i\le y$ 的点的 $x_i$ 修改为 $x$。 - 然后进行查询，询问满足 $x_i\le X,\;y_i\le Y$ 的点数。 ## Input 第一行两个整数 $n,m$。接下来 $n$ 行每行两个整数 $x_i,y_i$。接下来 $m$ 行每行五个整数 $o,x,y,X,Y$，表示一次操作。 ## Output 共 $m$ 行，每行一个整数，依次表示每次操作进行的查询的答案。 [samples] ## Note Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于所有数据，$1 \le n,m \le 10^6$，$1\le x_i,y_i,x,y,X,Y\le n$。子任务 1（20 分）：$n,m\le 10^3$；子任务 2（20 分）：$x_i,y_i,x,y,X,Y$ 独立地在 $1$ 到 $n$ 内均匀随机选取；子任务 3（20 分）：$o=1$；子任务 4（20 分）：$n,m\le 3\times 10^5$，依赖子任务 1；子任务 5（20 分）：无特殊限制，依赖子任务 1、2、3、4。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi2002] Optimal Ordered Problem Solver",
    "description": {
      "content": "给定 $n$ 个点 $(x_i,y_i)_{i=1}^n$，你需要按顺序处理 $m$ 次操作。每次操作给出 $o,x,y,X,Y$， - 首先进行修改：   - 若 $o=1$ 则将满足 $x_i\\le x,\\;y_i\\le y$ 的点的 $y_i$ 修改为 $y$；   - 若 $o=2$ 则将满足 $x_i\\le x,\\;y_i\\le y$ 的点的 $x_i$ 修改为 $x$。 - 然后进行",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9061"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个点 $(x_i,y_i)_{i=1}^n$，你需要按顺序处理 $m$ 次操作。每次操作给出 $o,x,y,X,Y$，\n\n- 首先进行修改：\n  - 若 $o=1$ 则将满足 $x_i\\le x,\\;y_i\\le y$ 的点的 $y_i$ 修改为 $y$；\n  - 若 $o=2$ 则将满足 $x_i\\le x,\\;y_i\\le y$ 的点的 $x_i$ 修改为 $x$。\n- 然后进行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments