[EC Final 2021] Vacation

Luogu

IDLGP9877

Time4000ms

Memory1024MB

DifficultyP7

2021O2优化ICPCEC Final

Prof. Pang has an annual leave of $c$ days and he wants to go on vacation. Now there are $n$ days in a year. Prof. Pang can gain $a_i$ happiness if he rests on the $i$-th day. The values of happiness, $a_i$, may be negative. Prof. Pang wants you to do $m$ operations: - $1~x~y$, change the happiness of the $x$-th day to $y$. - $2~l~r$, Prof. Pang wants to find a period of vacation in $[l, r]$. He wants to rest for several (possibly $0$) days in a row and gain as much happiness as possible. However, he only has $c$ days off, thus he can rest for no more than $c$ consecutive days in $[l,r]$. That means he wants to find $$\max\left(\max_{l \leq l' \leq r' \leq r\atop r'-l'+1\leq c} ~~ \left(\sum_{i=l'} ^{r'} a_i\right), 0\right).$$ ## Input The first line contains three integers $n, m, c (1\leq n\leq 2\times 10^5, 1\leq m \leq 5\times 10^5, 1\leq c\leq n)$ indicating the number of days in a year, the number of operations, and Prof. Pang's annual leave days. The next line contains $n$ integers $a_1, a_2, \dots, a_n(-10^9 \leq a_i\leq 10^9)$ indicating the values of happiness of every day. The next $m$ lines are the $m$ operations in the format described above. It is guaranteed that $1\leq x\leq n, -10^9\leq y\leq 10^9, 1\leq l\leq r \leq n$. ## Output For each operation of the second type, print the answer. [samples]

Samples

Input #1

5 6 3
0 -5 -3 8 -3
2 3 5
1 2 5
2 1 5
1 4 -3
2 3 5
2 1 5

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2021] Vacation",
    "description": {
      "content": "Prof. Pang has an annual leave of $c$ days and he wants to go on vacation. Now there are $n$ days in a year. Prof. Pang can gain $a_i$ happiness if he rests on the $i$-th day. The values of happiness",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9877"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Prof. Pang has an annual leave of $c$ days and he wants to go on vacation.\n\nNow there are $n$ days in a year. Prof. Pang can gain $a_i$ happiness if he rests on the $i$-th day. The values of happiness...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments