[CCPC 2023 北京市赛] 线段树

Luogu

IDLGP10045

Time4000ms

Memory1024MB

DifficultyP5

数学线段树2023组合数学省赛/邀请赛

有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，保证 $a_i$ 为**奇数**。有两种操作： 1. 给定 $l,r,x$，将 $a_l,a_{l+1},\cdots,a_r$ 加上**偶数** $x$； 2. 给定 $l,r$，求 $a_l,a_{l+1},\cdots,a_r$ 的乘积，答案对 $2^{20}$ 取模； ## Input 第一行两个正整数 $n,q$ 表示序列的长度和询问的个数. 保证 $1 \le n,q \le 2\times 10^5$。第二行 $n$ 个**奇数** $a_1,a_2,\cdots,a_n$. 保证 $1 \le a_i < 2^{20}$。接下来 $q$ 行，每一行表示一个操作，格式为以下两种之一： - $1 ~ l ~ r ~ x$：表示进行第一种操作. 保证 $1 \le l \le r \le n$，$0 \le x < 2 ^ {20}$。 - $2 ~ l ~ r$：表示进行第二种操作. 保证 $1 \le l \le r \le n$。 ## Output 对于每一次 $2$ 操作，输出一行一个整数表示答案。 [samples]

Samples

Input #1

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323 
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CCPC 2023 北京市赛] 线段树",
    "description": {
      "content": "有一个长度为 $n$ 的序列 $a_1,a_2,\\cdots,a_n$，保证 $a_i$ 为**奇数**。 有两种操作： 1. 给定 $l,r,x$，将 $a_l,a_{l+1},\\cdots,a_r$ 加上**偶数** $x$； 2. 给定 $l,r$，求 $a_l,a_{l+1},\\cdots,a_r$ 的乘积，答案对 $2^{20}$ 取模；",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10045"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个长度为 $n$ 的序列 $a_1,a_2,\\cdots,a_n$，保证 $a_i$ 为**奇数**。\n\n有两种操作：\n\n1. 给定 $l,r,x$，将 $a_l,a_{l+1},\\cdots,a_r$ 加上**偶数** $x$；\n\n2. 给定 $l,r$，求 $a_l,a_{l+1},\\cdots,a_r$ 的乘积，答案对 $2^{20}$ 取模；\n\n## Input\n\n第一行两个正整数 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments