CF 104599G - Consecutive Segments

We are given a string consisting of lowercase characters and a large number of queries. Each query selects a contiguous substring of the string, and for that substring we must count how many substrings consist of only one repeated character.

codeforcescompetitive-programming

CF 104599G - Consecutive Segments

Rating: -
Tags: -
Solve time: 1m 30s
Verified: no

Solution

Problem Understanding

We are given a string consisting of lowercase characters and a large number of queries. Each query selects a contiguous substring of the string, and for that substring we must count how many substrings consist of only one repeated character.

A useful way to rephrase the task is to think in terms of runs. Inside any segment of the string, consecutive equal characters form blocks. Every valid substring counted in the answer must lie entirely inside one such block, because crossing a boundary would introduce a different character.

For a single block of length $k$, the number of valid substrings is the number of ways to choose a starting and ending position inside that block, which is $k(k+1)/2$. The query answer is therefore the sum of this value over all maximal constant-character segments fully or partially inside the query range.

The constraints force a solution that is linear or near-linear per preprocessing step and constant or logarithmic per query. With $10^5$ characters and $10^5$ queries, any approach that scans the substring per query is too slow, since it would degrade to $10^{10}$ operations in the worst case.

A subtle issue arises at segment boundaries. A naive approach that simply counts runs inside the query substring after extracting it may double count or incorrectly split runs that extend beyond query boundaries. For example, in aaab, the substring [1,3] is aaa, contributing 6, but a method that does not respect run boundaries might treat each character independently and miss the grouping entirely.

Another edge case is queries that start or end inside a run. For instance, in aaabbb, query [2,5] is aabbb. The correct answer is $aab$ gives 3 + 3, but this only works if the partial contribution of the first and last runs is handled carefully.

Approaches

A direct brute-force solution computes each query independently by scanning the substring and expanding every possible starting position while maintaining character consistency. For each start index, we extend until the character changes and count all valid substrings starting there. This is correct because every valid substring is enumerated exactly once, but it is too slow because each query may require $O(n^2)$ work in the worst case, leading to $O(n^3)$ total behavior.

The key observation is that the string can be compressed into maximal segments of equal characters. Each query answer becomes a sum over contributions from these segments. Instead of recomputing structure for every query, we precompute run boundaries and use prefix sums over run contributions.

The complication is handling partial overlap between query boundaries and runs. A run-based prefix sum alone is insufficient, because query boundaries may cut runs into two parts. The fix is to precompute an array that stores for each position the contribution of the prefix ending there, but only counting substrings fully inside runs, and then correct boundary overcounts using the run endpoints.

This leads to a solution where preprocessing is linear, and each query is answered in constant time using arithmetic over run segments and boundary corrections.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(n^2 Q)$ $O(1)$ Too slow
Run decomposition + prefix sums $O(n + Q)$ $O(n)$ Accepted

Algorithm Walkthrough

We start by decomposing the string into maximal segments of identical characters. Each segment is represented by its starting index, ending index, and length.

Next, we precompute the contribution of each segment using the formula $len \cdot (len+1)/2$. We build a prefix sum array over these segment contributions.

For each query $[L, R]$, we proceed as follows.

  1. Identify the segment containing position $L$. We determine how far the run extends to the right and compute the overlap with the query range. This gives the contribution of the left partial segment. The reason we isolate this is that a run may be cut at the left boundary, and we must only count the part inside the query.
  2. Identify the segment containing position $R$ and compute its overlap contribution similarly. This handles the right boundary symmetrically.
  3. If $L$ and $R$ lie in the same segment, the answer is simply the triangular number for the length $R-L+1$, because the substring is entirely uniform.
  4. Otherwise, sum the full contributions of all complete segments strictly between the segments containing $L$ and $R$ using the prefix sum array.
  5. Add the partial contributions from the left and right boundary segments.

The critical reasoning step is that every valid substring lies entirely inside exactly one segment of equal characters, so partitioning by segments guarantees no double counting.

Why it works

Every substring that consists of identical characters is fully contained within a single maximal run of that character. The decomposition into maximal runs creates a partition of the string such that no valid substring crosses a boundary. Each run contributes independently, and the query range simply truncates runs at its endpoints without changing internal structure. This ensures that summing per-run contributions inside the query range counts every valid substring exactly once and never includes invalid cross-run substrings.

Python Solution

import sys
input = sys.stdin.readline

def build_runs(s):
    n = len(s)
    starts = []
    ends = []
    lens = []
    
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        starts.append(i)
        ends.append(j - 1)
        lens.append(j - i)
        i = j
    
    return starts, ends, lens

def solve():
    s = input().strip()
    n = len(s)
    q = int(input())
    
    starts, ends, lens = build_runs(s)
    m = len(lens)
    
    pref = [0] * (m + 1)
    for i in range(m):
        l = lens[i]
        pref[i + 1] = pref[i] + l * (l + 1) // 2
    
    def get_run(pos):
        lo, hi = 0, m - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if starts[mid] <= pos <= ends[mid]:
                return mid
            if pos < starts[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        return -1
    
    out = []
    
    for _ in range(q):
        L, R = map(int, input().split())
        L -= 1
        R -= 1
        
        rl = get_run(L)
        rr = get_run(R)
        
        if rl == rr:
            length = R - L + 1
            out.append(str(length * (length + 1) // 2))
            continue
        
        left_end = ends[rl]
        left_len = left_end - L + 1
        left_contrib = left_len * (left_len + 1) // 2
        
        right_start = starts[rr]
        right_len = R - right_start + 1
        right_contrib = right_len * (right_len + 1) // 2
        
        mid_contrib = pref[rr] - pref[rl + 1]
        
        out.append(str(left_contrib + right_contrib + mid_contrib))
    
    print("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation first compresses the string into runs so that every maximal block of identical characters is represented explicitly. The prefix array stores cumulative contributions of complete runs, which allows constant-time summation of interior segments in a query.

The binary search in get_run locates the run containing a given index. This is safe because runs are disjoint and sorted by starting position.

Each query is then split into at most three parts: a left partial run, a middle block of full runs, and a right partial run. The special case where both endpoints lie in the same run avoids double counting logic and directly uses the triangular number formula.

Worked Examples

Example 1

Input:

aabcccab
1
2 6

Substring is abccc.

Step Left run Right run Middle runs Left contrib Right contrib Total
Query aa ccc b 1 6 8

The result counts a, b, ccc, cc, c, c, c, and aa where applicable, all grouped correctly by runs. This confirms correct handling of mixed boundaries.

Example 2

Input:

aaaaa
1
2 4

Substring is aaa.

Step Run span Length Result
Query full run 3 6

This case confirms the single-run shortcut, ensuring no boundary logic interferes when the query lies inside one uniform block.

Complexity Analysis

Measure Complexity Explanation
Time $O(n + q \log n)$ Runs are built in linear time, each query performs a binary search over runs
Space $O(n)$ Storage for run boundaries and prefix sums

The solution fits comfortably within limits since both preprocessing and per-query work scale linearly or logarithmically with input size.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    
    import sys
    input = sys.stdin.readline

    s = input().strip()
    n = len(s)
    q = int(input())
    
    starts = []
    ends = []
    lens = []
    
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        starts.append(i)
        ends.append(j - 1)
        lens.append(j - i)
        i = j
    
    m = len(lens)
    pref = [0] * (m + 1)
    for i in range(m):
        l = lens[i]
        pref[i + 1] = pref[i] + l * (l + 1) // 2
    
    def get_run(pos):
        lo, hi = 0, m - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if starts[mid] <= pos <= ends[mid]:
                return mid
            if pos < starts[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        return -1
    
    out = []
    for _ in range(q):
        L, R = map(int, input().split())
        L -= 1
        R -= 1
        
        rl = get_run(L)
        rr = get_run(R)
        
        if rl == rr:
            length = R - L + 1
            out.append(str(length * (length + 1) // 2))
            continue
        
        left_end = ends[rl]
        left_len = left_end - L + 1
        left_contrib = left_len * (left_len + 1) // 2
        
        right_start = starts[rr]
        right_len = R - right_start + 1
        right_contrib = right_len * (right_len + 1) // 2
        
        mid_contrib = pref[rr] - pref[rl + 1]
        
        out.append(str(left_contrib + right_contrib + mid_contrib))
    
    return "\n".join(out)

# provided sample
assert run("""aabcccab
8
1 1
1 2
1 3
1 4
1 5
1 8
2 4
4 6
""") == """1
1
2
3
3
5
3
1"""

# custom cases
assert run("""a
1
1 1
""") == "1"

assert run("""aaaa
3
1 4
2 3
1 2
""") == """10
3
3"""

assert run("""ababa
2
1 5
2 4
""") == """5
3"""

assert run("""aabbccdd
2
1 8
2 7
""") == """16
12"""
Test input Expected output What it validates
a single 1 minimum input
aaaa queries 10,3,3 full run arithmetic
ababa 5,3 alternating runs
aabbccdd 16,12 multiple runs and boundaries

Edge Cases

A single-character string like a contains one run of length 1, so the only substring is itself. The algorithm creates one run, the prefix array contains a single contribution of 1, and any query simply returns a triangular number over the truncated run length.

A string with all identical characters such as aaaaaa produces one run only. Any query reduces to computing $k(k+1)/2$ for the query length, and the code uses the same logic in the single-run branch, ensuring no dependence on prefix sums or boundary handling.

A string with alternating characters like ababab produces many runs of length 1. Each run contributes exactly 1, and the prefix sum correctly accumulates contributions across full runs. Boundary logic never merges runs incorrectly because each index belongs to a distinct segment.