{"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, $a_i$, may be negative.\n\nProf. Pang wants you to do $m$ operations:\n\n- $1~x~y$, change the happiness of the $x$-th day to $y$.\n- $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]$.\n\nThat means he wants to find \n\n$$\\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).$$\n\n## Input\n\nThe 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.\n\nThe 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.\n\nThe next $m$ lines are the $m$ operations in the format described above.\n\nIt is guaranteed that $1\\leq x\\leq n, -10^9\\leq y\\leq 10^9, 1\\leq l\\leq r \\leq n$.\n\n## Output\n\nFor each operation of the second type, print the answer.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9877","tags":["2021","O2优化","ICPC","EC Final"],"sample_group":[["5 6 3\n0 -5 -3 8 -3\n2 3 5\n1 2 5\n2 1 5\n1 4 -3\n2 3 5\n2 1 5","8\n10\n0\n5"]],"created_at":"2026-03-03 11:09:25"}}