[eJOI 2021] AddK

Luogu

IDLGP8165

Time1000ms

Memory512MB

DifficultyP4

2021eJOI（欧洲）

给定一个包含 $N$ 个整数 $A_1,\dots,A_N$ 的数组 $A$ 和一个整数 $K$。你需要进行 $Q$ 次操作，包括下列两种类型： - $1$ $i_1$ $i_2$ $\dots$ $i_K$：将 $A_{i_1},A_{i_2},\dots,A_{i_{K-1}},A_{i_K}$ 的值依次替换为 $A_{i_2},A_{i_3},\dots,A_{i_K},A_{i_1}$ 的值。其中，$i_1,\dots,i_k$ 互不相同。 - $2$ $l$ $r$ $m$：输出 $[l,r]$ 区间内所有长度为 $m$ 的连续子序列的元素和。 ## Input 第一行两个整数 $N,K$。第二行 $N$ 个整数，表示数组 $A$ 的 $N$ 个整数。第三行一个整数 $Q$，表示操作次数。接下来 $Q$ 行，每行若干个整数，表示一次操作。 ## Output 输出包含若干行整数，即为所有操作 $2$ 的结果。 [samples] ## Note #### 样例解释第一次询问需要求出 $\{2,5,1,9,3,4\}$ 中所有长度为 $4$ 的连续子序列的元素和。这些子序列包括 $\{2,5,1,9\},\{5,1,9,3\},\{1,9,3,4\}$。因此答案为 $52$。第二次询问需要将 $A_2,A_5,A_8$ 依次替换为 $A_5,A_8,A_2$ 的值。替换后数组变为 $\{7,9,5,1,6,3,4,2\}$。第三次询问需要求出 $\{9,5,1,6,3,4\}$ 中所有长度为 $3$ 的连续子序列的元素和。这些子序列包括 $\{9,5,1\},\{5,1,6\},\{1,6,3\},\{6,3,4\}$。因此答案为 $50$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（36 pts）：$1 \le N,Q \le 10^4$ 且 $K=1$。 - Subtask 2（56 pts）：$10001 \le N,Q \le 10^5$ 且 $K=1$。 - Subtask 3（8 pts）：$1 \le N,Q \le 10^5$ 且 $2 \le K \le 10$。对于 $100\%$ 的数据，$0 \le A_i \le 10^6$，$1 \le l \le r \le N$，$1 \le m \le r-l+1$。 #### 说明本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 A AddK。

Samples

Input #1

8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3

Output #1

52
50

API Response (JSON)

{
  "problem": {
    "name": "[eJOI 2021] AddK",
    "description": {
      "content": "给定一个包含 $N$ 个整数 $A_1,\\dots,A_N$ 的数组 $A$ 和一个整数 $K$。你需要进行 $Q$ 次操作，包括下列两种类型： - $1$ $i_1$ $i_2$ $\\dots$ $i_K$：将 $A_{i_1},A_{i_2},\\dots,A_{i_{K-1}},A_{i_K}$ 的值依次替换为 $A_{i_2},A_{i_3},\\dots,A_{i_K},A_{i_1}$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8165"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 $N$ 个整数 $A_1,\\dots,A_N$ 的数组 $A$ 和一个整数 $K$。你需要进行 $Q$ 次操作，包括下列两种类型：\n\n- $1$ $i_1$ $i_2$ $\\dots$ $i_K$：将 $A_{i_1},A_{i_2},\\dots,A_{i_{K-1}},A_{i_K}$ 的值依次替换为 $A_{i_2},A_{i_3},\\dots,A_{i_K},A_{i_1}$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments