[Ynoi Easy Round 2024] TEST_132

Luogu

IDLGP9994

Time12000ms

Memory512MB

DifficultyP6

2024O2优化Ynoi

给定平面上 $n$ 个互不相同的点 $(x_i,y_i)_{i=1}^n$，每个点有点权，初始为 $v_i$；共 $m$ 次操作：修改操作：给定 $X$，将满足 $x_i=X$ 的点的点权 $v_i$ 修改为 $v_i^2$；查询操作：给定 $Y$，求满足 $y_i=Y$ 的点的点权 $v_i$ 的和；答案对 $10^9+7$ 取模。 ## Input 第一行两个整数 $n,m$；接下来 $n$ 行，每行三个整数 $x_i,y_i,v_i$；接下来 $m$ 行，每行两个整数，修改操作表示为 $1,X$，查询操作表示为 $2,Y$； ## Output 对每个查询操作，输出一行，表示答案。 [samples] ## Note Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $100\%$ 的数据，满足 $1\le n,m\le 1.2\times10^6$，$1\le x_i,y_i\le n$，$0\le v_i\le 10^9+6$，$1\le X,Y\le n$。对于 $25\%$ 的数据，满足 $n,m\le 5000$；对于另外 $25\%$ 的数据，没有修改操作；对于另外 $25\%$ 的数据，满足 $x_i,y_i,X,Y$ 在 $1,2,\dots,n$ 中独立地均匀随机选取；对于另外 $25\%$ 的数据，无特殊限制。

Samples

Input #1

5 10
1 3 597843412
1 1 613307236
1 2 488247075
1 4 29761102
1 5 101159431
1 1
2 2
1 1
2 2
2 1
2 2
1 1
1 1
2 3
1 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi Easy Round 2024] TEST_132",
    "description": {
      "content": "给定平面上 $n$ 个互不相同的点 $(x_i,y_i)_{i=1}^n$，每个点有点权，初始为 $v_i$； 共 $m$ 次操作： 修改操作：给定 $X$，将满足 $x_i=X$ 的点的点权 $v_i$ 修改为 $v_i^2$； 查询操作：给定 $Y$，求满足 $y_i=Y$ 的点的点权 $v_i$ 的和； 答案对 $10^9+7$ 取模。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 12000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9994"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定平面上 $n$ 个互不相同的点 $(x_i,y_i)_{i=1}^n$，每个点有点权，初始为 $v_i$；\n\n共 $m$ 次操作：\n\n修改操作：给定 $X$，将满足 $x_i=X$ 的点的点权 $v_i$ 修改为 $v_i^2$；\n\n查询操作：给定 $Y$，求满足 $y_i=Y$ 的点的点权 $v_i$ 的和；\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n第一行两个整数 $n,m...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments