Overview

This problem requires finding the “number of blocks” in any interval while performing bulk repainting of interval colors.
By using a lazy segment tree that maintains the leftmost color, the rightmost color, and the block count for each interval, both updates and queries can be processed in \(O(\log N)\).

Approach

First, the number of blocks is “the number of positions where adjacent colors differ \(+1\).”
For example, given

• \(1,1,2,2,2,1\)

the color changes occur at

• \(1 \to 2\)
• \(2 \to 1\)

which is 2 places, so the number of blocks is \(2+1=3\).

Why the naive approach is too slow

• If update 1 L R X is done naively, each element in the interval \([L,R]\) must be rewritten, costing \(O(R-L+1)\)
• For query 2 L R, scanning the interval to count color changes also costs \(O(R-L+1)\)

In the worst case, both take \(O(N)\), resulting in an overall complexity of \(O(NQ)\), which is too slow.

How to summarize an interval

When splitting an interval into its left half and right half, what information do we need to determine the block count of the entire interval?

It turns out that the following 3 pieces of information for each sub-interval are sufficient:

• The leftmost color of the interval
• The rightmost color of the interval
• The block count of the interval

This is because when connecting the left and right intervals, only the 2 colors at the boundary matter.

Let the left interval be \((lc_1, rc_1, cnt_1)\) and the right interval be \((lc_2, rc_2, cnt_2)\). Then:

• If \(rc_1 = lc_2\), the two blocks at the boundary merge into one
• Otherwise, they remain as separate blocks

Therefore, after merging:

• Leftmost color: \(lc_1\)
• Rightmost color: \(rc_2\)
• Block count: \(cnt_1 + cnt_2 - [rc_1 = lc_2]\)

Here, \([P]\) equals 1 if condition \(P\) is true, and 0 if false.

Why updates become simple

When painting the entire interval \([L,R]\) with color \(X\), the interval becomes entirely the same color.
This means the information for that interval is immediately:

• Leftmost color: \(X\)
• Rightmost color: \(X\)
• Block count: \(1\)

Because of this property, a lazy segment tree, which works well with range assignment, can be used.

---

Algorithm

1. Information stored at each segment tree node

Each node (representing some interval) stores the following:

• lc : the leftmost color of the interval
• rc : the rightmost color of the interval
• cnt: the block count of the interval

A leaf represents a single cell, so if the color is \(c\):

• lc = c
• rc = c
• cnt = 1

2. Merging two child intervals

Let the left child be \(A\) and the right child be \(B\). Then:

• lc = A.lc
• rc = B.rc
• cnt = A.cnt + B.cnt - (A.rc == B.lc)

This gives the parent’s information.

Example

If the left interval is 1,1,2:

• lc=1
• rc=2
• cnt=2

If the right interval is 2,2,3:

• lc=2
• rc=3
• cnt=2

When connecting these two, the boundary has 2 and 2 which are the same, so one block merges:

• cnt = 2 + 2 - 1 = 3

Indeed, laid out as 1,1,2,2,2,3, the block count is 3.

3. Range assignment via lazy propagation

For update 1 L R X, the entire interval is painted with color \(X\).

If the interval represented by a node is completely contained within the update interval, the entire interval becomes the same color, so we set:

• lc = X
• rc = X
• cnt = 1

Additionally, we record \(X\) in lazy so that the same update can be propagated to children later.

This way, we can perform updates without descending all the way to the leaves every time.

4. Range query

For query 2 L R, we find the block count of interval \([L,R]\).

In a segment tree range query, the target interval is decomposed into several node intervals and collected.
However, in this problem, simply summing up block counts is not enough, because blocks at the boundaries of adjacent intervals may merge.

Therefore, during the query, we maintain two accumulated pieces of information:

• Information gathered from the left
• Information gathered from the right

For each:

• Left accumulation: rightmost color and block count
• Right accumulation: leftmost color and block count

Each time a node is collected, we merge while preserving the order.
Finally, merging the left accumulation and right accumulation once gives the block count for the entire queried interval.

5. Interval representation in implementation

Internally, the code uses 0-indexed half-open intervals \([l,r)\).

Since the input uses 1-indexed closed intervals \([L,R]\), we convert:

• L -> L-1
• R -> R

to get the half-open interval \([L-1, R)\).

---

Complexity

• Time complexity: \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\)

Initial construction takes \(O(N)\), and each update and each query takes \(O(\log N)\).

Implementation Notes

• Only 3 pieces of summary information per node are sufficient
  • Leftmost color
  • Rightmost color
  • Block count
• A node that has been range-assigned always has block count 1
  • Because the entire interval becomes the same color
• Order matters in queries
  • Intervals taken from the left and intervals taken from the right are managed separately, then merged at the end
• Be careful with unused leaves
  • Since the segment tree size is rounded up to a power of 2, leaves for non-existent elements may appear
  • In this code, cnt = 0 is treated as an “empty interval,” and pull handles this carefully
• lazy = 0 can be used as a marker for “no pending update”
  • Since the problem guarantees \(C_i, X\) are all at least 1, 0 can be safely used as a special sentinel value

In this way, “maintaining only the information needed when merging intervals” is the essence of this problem.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    idx = 0
    N = data[idx]
    Q = data[idx + 1]
    idx += 2

    A = data[idx:idx + N]
    idx += N

    size = 1
    while size < N:
        size <<= 1
    log = size.bit_length() - 1

    m = size << 1
    lc = [0] * m
    rc = [0] * m
    cnt = [0] * m
    lazy = [0] * size

    for i, c in enumerate(A):
        k = size + i
        lc[k] = c
        rc[k] = c
        cnt[k] = 1

    def pull(k):
        l = k << 1
        r = l | 1
        cl = cnt[l]
        cr = cnt[r]
        if cl == 0:
            cnt[k] = cr
            lc[k] = lc[r]
            rc[k] = rc[r]
        elif cr == 0:
            cnt[k] = cl
            lc[k] = lc[l]
            rc[k] = rc[l]
        else:
            cnt[k] = cl + cr - (rc[l] == lc[r])
            lc[k] = lc[l]
            rc[k] = rc[r]

    for k in range(size - 1, 0, -1):
        pull(k)

    def apply(k, x):
        lc[k] = x
        rc[k] = x
        cnt[k] = 1
        if k < size:
            lazy[k] = x

    def push(k):
        x = lazy[k]
        if x:
            l = k << 1
            r = l | 1

            lc[l] = x
            rc[l] = x
            cnt[l] = 1
            if l < size:
                lazy[l] = x

            lc[r] = x
            rc[r] = x
            cnt[r] = 1
            if r < size:
                lazy[r] = x

            lazy[k] = 0

    def range_apply(l, r, x):
        l += size
        r += size
        l0 = l
        r0 = r

        for i in range(log, 0, -1):
            if ((l0 >> i) << i) != l0:
                push(l0 >> i)
            if ((r0 >> i) << i) != r0:
                push((r0 - 1) >> i)

        while l < r:
            if l & 1:
                apply(l, x)
                l += 1
            if r & 1:
                r -= 1
                apply(r, x)
            l >>= 1
            r >>= 1

        for i in range(1, log + 1):
            if ((l0 >> i) << i) != l0:
                pull(l0 >> i)
            if ((r0 >> i) << i) != r0:
                pull((r0 - 1) >> i)

    def range_query_count(l, r):
        l += size
        r += size

        for i in range(log, 0, -1):
            if ((l >> i) << i) != l:
                push(l >> i)
            if ((r >> i) << i) != r:
                push((r - 1) >> i)

        left_r = 0
        left_c = 0
        right_l = 0
        right_c = 0

        while l < r:
            if l & 1:
                c = cnt[l]
                if c:
                    if left_c == 0:
                        left_r = rc[l]
                        left_c = c
                    else:
                        left_c = left_c + c - (left_r == lc[l])
                        left_r = rc[l]
                l += 1
            if r & 1:
                r -= 1
                c = cnt[r]
                if c:
                    if right_c == 0:
                        right_l = lc[r]
                        right_c = c
                    else:
                        right_c = c + right_c - (rc[r] == right_l)
                        right_l = lc[r]
            l >>= 1
            r >>= 1

        if left_c == 0:
            return right_c
        if right_c == 0:
            return left_c
        return left_c + right_c - (left_r == right_l)

    ans = []
    append = ans.append

    for _ in range(Q):
        t = data[idx]
        idx += 1
        if t == 1:
            L = data[idx] - 1
            R = data[idx + 1]
            X = data[idx + 2]
            idx += 3
            range_apply(L, R, X)
        else:
            L = data[idx] - 1
            R = data[idx + 1]
            idx += 2
            append(str(range_query_count(L, R)))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.