Problem Description

Given a sequence $a=(a_1,a_2,\cdots,a_n)$ and a constant $k$, there are $q$ operations:

• 1 x y: Change $a_x$ to $y$.
• 2 l r: Find the maximum subarray sum of $a[l,r]$ whose length is in $[0,k]$ (i.e., length between $0$ and $k$, inclusive).

Constraints

• $1\le n\le 2\times 10^5$
• $1\le q\le 4\times 10^5$
• $|a_i|,|y|\le 10^9$
• Time limit: $4\text{s}$, Memory limit: $1\text{GB}$

Solution

Partition the sequence into blocks of length $k$. Then the answer can only come from within a block or between blocks.

Within a block

This is trivial: directly maintain with a segment tree.

Between blocks

Maintain the answer for $[l, r+k]$. Let $A=[l,r]$ and $B=[l+k,r+k]$.

Consider merging. The answer falls into the following cases:

• The answer from the left half plus the entire segment $A$ from the right half.
• The answer from the right half plus the entire segment $B$ from the left half.
• A prefix of $B$ from the left plus a suffix of $A$ from the right.

Use a segment tree to maintain the required information.

Query handling

For partial blocks, directly use the two segment trees mentioned above.

For whole blocks (both inside and between blocks), we cannot brute force over all blocks to take the maximum. Therefore, build two additional segment trees to maintain RMQ.

To reduce case analysis, temporarily change positions $l-1$ and $r+1$ in the inter-block segment tree to $-\infty$.

Complexity

Time complexity: $O((n+q)\log n)$.