Panel Activation#13043

Panel Activation (Editoryal)

Solution

First, calculate the answer without performing any operation.

It is simply the maximum length of a contiguous segment consisting only of ones.

Now suppose we choose position $i$ .

If $s_{i} = 0$ s_i=0, the operation is allowed only if

c_{i} \leq k .

c_i \le k.

If $s_{i} = 1$ s_i=1, the operation is always allowed.

After choosing $i$ , at most three positions can become equal to $1$ :

i, L_{i}, R_{i},

i,\ L_i,\ R_i,

where

L_{i} = max {j < i : s_{j} = 0, c_{j} < c_{i}},

L_i=\max\{j<i:s_j=0,\ c_j<c_i\},

and

R_{i} = min {j > i : s_{j} = 0, c_{j} < c_{i}} .

R_i=\min\{j>i:s_j=0,\ c_j<c_i\}.

So first we need to find $L_{i}$ L_i and $R_{i}$ R_i for every position.

Finding $L_{i}$ L_i

Compress all values $c_{i}$ c_i.

Process positions from left to right and maintain a Fenwick tree.

For every compressed value, the Fenwick tree stores the maximum index of a zero with this value that has already been processed.

For position $i$ , query all values strictly smaller than $c_{i}$ c_i.

The maximum index among them is exactly $L_{i}$ L_i.

After that, if $s_{i} = 0$ s_i=0, insert position $i$ into the Fenwick tree.

Finding $R_{i}$ R_i

We do the same thing from right to left.

Now the Fenwick tree stores the minimum index.

For every position $i$ , querying all values strictly smaller than $c_{i}$ c_i gives $R_{i}$ R_i.

Thus, all values $L_{i}$ L_i and $R_{i}$ R_i can be calculated in

O (n lo g n) .

O(n\log n).

Segments around changed positions

For every position $x$ , define $[l o_{x}, h i_{x}]$ [lo_x,hi_x] as the maximal segment of ones containing $x$ if we change only position $x$ to $1$ .

If $s_{x} = 1$ s_x=1, this is simply its current maximal segment of ones.

If $s_{x} = 0$ s_x=0, we extend from $x$ through all consecutive ones immediately to its left and right.

These values can be calculated in $O (n)$ time.

Now consider an operation at position $i$ .

Take all existing positions among

i, L_{i}, R_{i} .

i,\ L_i,\ R_i.

There are at most three of them.

Sort them:

x_{1} < x_{2} < \dots < x_{t} .

x_1 < x_2 < \dots < x_t.

Each $x_{j}$ x_j initially corresponds to the segment

[l o_{x_{j}}, h i_{x_{j}}] .

[lo_{x_j},hi_{x_j}].

Two consecutive changed positions $x_{j}$ x_j and $x_{j + 1}$ x_{j+1} belong to the same final segment of ones exactly when there is no unchanged zero strictly between them.

Let $p r e f_{i}$ pref_i be the number of zeroes among the first $i$ positions.

Then there is no zero strictly between $x_{j}$ x_j and $x_{j + 1}$ x_{j+1} exactly when

p r e f_{x_{j + 1} - 1} - p r e f_{x_{j}} = 0.

pref_{x_{j+1}-1}-pref_{x_j}=0.

If this condition holds, the corresponding components are merged.

Since there are at most three changed positions, every possible operation can be checked in $O (1)$ time.

Correctness

The operation can change only positions $i$ , $L_{i}$ L_i, and $R_{i}$ R_i.

Therefore, every new segment of ones must contain at least one of these positions.

For every changed position $x$ , the interval $[l o_{x}, h i_{x}]$ [lo_x,hi_x] contains exactly all consecutive ones connected to $x$ after changing only $x$ .

Two such intervals are connected after the operation exactly when there is no unchanged zero between their changed positions.

The prefix sum of zeroes checks exactly this condition.

Therefore, for every possible operation, we correctly calculate every segment of ones that can appear.

Together with the answer obtained without performing an operation, this gives the optimal answer.

Complexity

The two Fenwick tree passes take

O (n lo g n)

O(n\log n)

time.

All other preprocessing takes $O (n)$ time, and every position is checked in $O (1)$ .

Therefore, the total complexity is

O (n lo g n)

O(n\log n)

time and

O (n)

memory.

s_{i} = 0

c_{i} \leq k .

s_{i} = 1

i, L_{i}, R_{i},

L_{i} = max {j < i : s_{j} = 0, c_{j} < c_{i}},

R_{i} = min {j > i : s_{j} = 0, c_{j} < c_{i}} .

L_{i}

R_{i}

L_{i}

c_{i}

c_{i}

L_{i}

s_{i} = 0

R_{i}

c_{i}

R_{i}

L_{i}

R_{i}

O (n lo g n) .

[l o_{x}, h i_{x}]

s_{x} = 1

s_{x} = 0

i, L_{i}, R_{i} .

x_{1} < x_{2} < \dots < x_{t} .

x_{j}

[l o_{x_{j}}, h i_{x_{j}}] .

x_{j}

x_{j + 1}

p r e f_{i}

x_{j}

x_{j + 1}

p r e f_{x_{j + 1} - 1} - p r e f_{x_{j}} = 0.

L_{i}

R_{i}

[l o_{x}, h i_{x}]

O (n lo g n)

O (n lo g n)