#[contest:688129]↵
↵
Hello everyone!↵
↵
Welcome to the editorial for our mashup contest. We selected a mix of Arrays, HashMaps, Math, Strings, Sliding Window and Prefix Sum problems. The goal was to strengthen logical thinking and problem-solving skills without getting bogged down in complex data structures.↵
↵
Below you will find hints, tutorials, and solutions for each problem. We used spoiler tags to keep things clean. Try to solve it yourself before clicking!↵
↵
Happy coding!↵
↵
## Problem-A:[problem:688129A]↵
**Tags:** `implementation` `strings` ↵
**Difficulty:** ⭐️ (Very Easy)↵
↵
This is a simple pattern-checking problem that tests your understanding of strings and substrings.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
### The Idea↵
Polycarp answers "Yes" by repeating it many times:↵
↵
YesYesYesYesYes...↵
↵
But you only hear a substring of that long string.↵
↵
---↵
↵
### What You Need to Check↵
Given a string `s`, determine:↵
↵
Is `s` a substring of the infinite string "YesYesYes..."?↵
↵
---↵
↵
### Important Notes↵
- Case matters: "YES" is NOT the same as "Yes".↵
- The pattern strictly repeats "Yes".↵
↵
</spoiler>↵
↵
<spoiler summary="Hint">↵
↵
- Build a long enough string like "YesYesYesYes...". ↵
- Check if `s` exists inside it. ↵
- Since |s| ≤ 50, repeating "Yes" about 20 times is enough. ↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
Instead of dealing with an infinite string, we simulate it.↵
↵
#### Step-by-step:↵
1. Create a long string:↵
base = "YesYesYesYesYes..."↵
2. For each test case:↵
- Read string `s`↵
- Check if `s` is a substring of `base`↵
3. If yes, print "YES", otherwise print "NO"↵
↵
---↵
↵
### Why This Works↵
↵
Any valid substring of "YesYesYes..." must appear in a sufficiently long repetition.↵
↵
Since:↵
- Maximum |s| = 50↵
- "Yes" length = 3 ↵
↵
Repeating "Yes" around 20 times (length = 60) is enough.↵
↵
---↵
↵
### Common Mistakes↵
↵
- Using "YES" instead of "Yes"↵
- Forgetting substring must be continuous↵
- Not repeating "Yes" enough times↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
```python↵
↵
↵
def solve():↵
t = int(input())↵
↵
base = "Yes" * 20 # long enough for all cases↵
↵
for _ in range(t):↵
s = input().strip()↵
↵
print("YES" if s in base else "NO")↵
↵
↵
solve()↵
↵
↵
↵
Complexity:↵
Time: O(t × |s|)↵
Space: O(1)↵
</spoiler>↵
↵
↵
↵
## Problem-B:[problem:688129B]↵
**Tags:** `implementation` `math`<br>↵
**Difficulty:** ⭐️ (Very Easy) ↵
↵
This is a very simple counting problem.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- An integer array `a` of size `n`↵
↵
---↵
↵
#### Operation↵
You can:↵
- Pick two indices `i < j`↵
- Such that:↵
— `a[i] == a[j]`↵
— Both indices are not used before↵
↵
Each such pair gives **+1 score**.↵
↵
---↵
↵
#### Task↵
Find the **maximum score**.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint">↵
↵
- Count how many times each number appears ↵
- From each value, you can form:↵
↵
count // 2 pairs ↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We need to maximize the number of valid pairs.↵
↵
#### Key Observation↵
- Each pair needs **2 equal elements**↵
- So for a value appearing `k` times:↵
↵
number of pairs = `k // 2`↵
↵
---↵
↵
### Step-by-Step Logic↵
1. Read `n` and array `a` ↵
2. Count frequency of each number ↵
3. For each frequency:↵
- Add `count // 2` to score ↵
4. Print total score ↵
↵
---↵
↵
### Example↵
↵
Input:↵
6 ↵
1 2 3 1 2 3 ↵
↵
Frequencies:↵
1 → 2 ↵
2 → 2 ↵
3 → 2 ↵
↵
Pairs:↵
1 → 1 pair ↵
2 → 1 pair ↵
3 → 1 pair ↵
↵
Total = 3 ↵
↵
---↵
↵
### Why this works↵
Each pair uses exactly 2 equal elements, and we cannot reuse indices.↵
↵
---↵
↵
### Complexity↵
- Time: O(n) ↵
- Space: O(n) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
def solve():↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
freq = {}↵
for x in arr:↵
freq[x] = freq.get(x, 0) + 1↵
↵
score = 0↵
for count in freq.values():↵
score += count // 2↵
↵
print(score)↵
↵
↵
solve()↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
## Problem-C:[problem:688129C]↵
**Tags:** `brute force` `implementation` `math` `sliding window`<br>↵
**Difficulty:** ⭐️⭐️ (Easy) ↵
↵
This is a parity-based selection problem that can be solved using counting and simple constraints.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- An array `a` of size `n`↵
- An integer `x`↵
↵
---↵
↵
#### Task↵
Select exactly `x` elements such that:↵
- Their sum is **odd**↵
↵
---↵
↵
#### Key Observation↵
- Sum is odd ⇔ number of odd elements selected is **odd**↵
- Even numbers do not change parity of the sum↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Count how many odd and even numbers exist.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Try to pick an odd count of odd numbers (at least 1), and fill the rest with even numbers.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Let:↵
- `o` = number of odd elements ↵
- `e` = number of even elements ↵
↵
You need to pick `k` odd numbers such that:↵
- `k` is odd ↵
- `0 ≤ k ≤ o` ↵
- `x - k ≤ e` ↵
↵
Check if such `k` exists.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We only care about parity, not actual values.↵
↵
#### Step-by-step:↵
1. Count:↵
- `o` = number of odd elements ↵
- `e` = number of even elements ↵
2. We want to pick `x` elements with **odd sum**↵
3. That means:↵
- pick an odd number of odd elements (`k`)↵
- remaining (`x - k`) must be even elements ↵
4. Compute:↵
- `l = max(1, x - e)` → minimum odd elements needed ↵
- `r = min(x, o)` → maximum odd elements possible ↵
5. Check if there exists an **odd `k` in [l, r]**↵
↵
---↵
↵
### Why this works↵
- Odd + Odd = Even ↵
- Even + Even = Even ↵
- Odd + Even = Odd ↵
↵
So we must ensure an odd count of odd numbers is selected.↵
↵
---↵
↵
### Example↵
↵
Input:↵
n = 3, x = 3 ↵
a = [101, 102, 103] ↵
↵
Odds = 2, Evens = 1 ↵
↵
We must pick all 3:↵
- Odd count = 2 → even sum → not valid ↵
↵
Answer: No ↵
↵
---↵
↵
### Complexity↵
- Time: O(n) per test case ↵
- Space: O(1) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
t = int(input())↵
for _ in range(t):↵
n, x = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
# count odd and even numbers↵
o = sum(1 for v in a if v % 2)↵
e = n - o↵
↵
# possible range of odd numbers we can take↵
l = max(1, x - e)↵
r = min(x, o)↵
↵
# check if there exists an odd number in [l, r]↵
print("Yes" if l <= r and (l % 2 == 1 or r > l) else "No")↵
~~~~~↵
↵
</spoiler>↵
↵
## Problem-D:[problem:688129D]↵
**Tags:** `implementation` `data structures` `DP` `prefix sum`<br>↵
**Difficulty:** ⭐️⭐️⭐️ (Medium) ↵
↵
This is a classic prefix sum problem that allows answering range queries efficiently.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- A string `s` consisting of '.' and '#'↵
- `m` queries, each with `(l, r)`↵
↵
---↵
↵
#### Task↵
For each query, count how many indices `i` satisfy:↵
- `l ≤ i < r`↵
- `s[i] == s[i+1]`↵
↵
In other words, count how many **adjacent equal characters** exist in the range.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Directly checking each query will be too slow.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Precompute results using a prefix sum array.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Build an array where:↵
- `pref[i]` = number of positions `j ≤ i` such that `s[j] == s[j-1]`↵
↵
Then each query becomes:↵
- `pref[r-1] - pref[l-1]`↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We preprocess the string to answer queries in constant time.↵
↵
#### Step-by-step:↵
1. Create a prefix array `pref`↵
2. For each position `i`:↵
- If `s[i] == s[i-1]`, increment count↵
3. Store cumulative counts in `pref`↵
4. For each query `(l, r)`:↵
- Answer = `pref[r-1] - pref[l-1]`↵
↵
---↵
↵
### Why this works↵
↵
- `pref[i]` stores how many equal adjacent pairs exist up to index `i`↵
- Subtracting gives count within a range↵
↵
---↵
↵
### Example↵
↵
s = "......"↵
↵
Pairs:↵
(1,2), (2,3), (3,4), (4,5), (5,6) → all equal↵
↵
So prefix:↵
[0,1,2,3,4,5]↵
↵
Query (1,6):↵
Answer = pref[5] — pref[0] = 5↵
↵
---↵
↵
### Complexity↵
- Preprocessing: O(n) ↵
- Each query: O(1) ↵
- Total: O(n + m) ↵
- Space: O(n) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
s = input().strip()↵
n = len(s)↵
↵
# build prefix array↵
pref = [0] * n↵
for i in range(1, n):↵
pref[i] = pref[i-1] + (1 if s[i] == s[i-1] else 0)↵
↵
m = int(input())↵
res = []↵
↵
for _ in range(m):↵
l, r = map(int, input().split())↵
↵
# convert to 0-based and use prefix sum↵
res.append(str(pref[r-1] - pref[l-1]))↵
↵
print('\n'.join(res))↵
~~~~~↵
↵
</spoiler>↵
↵
↵
## Problem-E:[problem:688129E]↵
**Tags:** `implementation` `data structures` `prefix sum` `binary search`<br>↵
**Difficulty:** ⭐️⭐️⭐️ (Medium) ↵
↵
This is a prefix sum + difference array problem that efficiently handles range updates and queries.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- `n` ranges `[l, r]` (recipes)↵
- A threshold `k`↵
- `q` queries `[a, b]`↵
↵
---↵
↵
#### Task↵
A temperature is **admissible** if:↵
- It is covered by at least `k` ranges↵
↵
For each query `[a, b]`, count how many admissible temperatures exist in that range.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Use a difference array to efficiently count how many ranges cover each temperature.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Convert the coverage into a prefix sum array.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Build another prefix array where:↵
- `pref[i]` = number of admissible temperatures ≤ i↵
↵
Then each query becomes:↵
- `pref[b] - pref[a-1]`↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We solve this in three steps.↵
↵
---↵
↵
### Step 1: Range Frequency using Difference Array↵
- For each range `[l, r]`:↵
- `diff[l] += 1`↵
- `diff[r+1] -= 1`↵
↵
Then compute prefix sum to get:↵
- `cnt[i]` = how many ranges include temperature `i`↵
↵
---↵
↵
### Step 2: Mark Admissible Temperatures↵
- If `cnt[i] ≥ k`, then temperature `i` is valid↵
- Build a prefix array:↵
- `pref[i] = number of admissible temperatures up to i`↵
↵
---↵
↵
### Step 3: Answer Queries↵
For each query `[a, b]`:↵
- Answer = `pref[b] - pref[a-1]`↵
↵
---↵
↵
### Why this works↵
- Difference array handles range updates in O(1)↵
- Prefix sum converts it into actual frequencies↵
- Another prefix sum enables fast queries↵
↵
---↵
↵
### Complexity↵
- Building arrays: O(MAX) ↵
- Each query: O(1) ↵
- Total: O(n + q + MAX) ↵
- Space: O(MAX) ↵
↵
(MAX ≈ 200000)↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
n, k, q = map(int, input().split())↵
↵
MAX = 200005↵
↵
# difference array↵
diff = [0] * MAX↵
for _ in range(n):↵
l, r = map(int, input().split())↵
diff[l] += 1↵
diff[r + 1] -= 1↵
↵
# build coverage count↵
cnt = [0] * MAX↵
for i in range(1, MAX):↵
cnt[i] = cnt[i-1] + diff[i]↵
↵
# build admissible prefix↵
pref = [0] * MAX↵
for i in range(1, MAX):↵
pref[i] = pref[i-1] + (1 if cnt[i] >= k else 0)↵
↵
# answer queries↵
for _ in range(q):↵
a, b = map(int, input().split())↵
print(pref[b] - pref[a-1])↵
~~~~~↵
↵
</spoiler>↵
↵
↵
Hello everyone!↵
↵
Welcome to the editorial for our mashup contest. We selected a mix of Arrays, HashMaps, Math, Strings, Sliding Window and Prefix Sum problems. The goal was to strengthen logical thinking and problem-solving skills without getting bogged down in complex data structures.↵
↵
Below you will find hints, tutorials, and solutions for each problem. We used spoiler tags to keep things clean. Try to solve it yourself before clicking!↵
↵
Happy coding!↵
↵
## Problem-A:[problem:688129A]↵
**Tags:** `implementation` `strings` ↵
**Difficulty:** ⭐️ (Very Easy)↵
↵
This is a simple pattern-checking problem that tests your understanding of strings and substrings.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
### The Idea↵
Polycarp answers "Yes" by repeating it many times:↵
↵
YesYesYesYesYes...↵
↵
But you only hear a substring of that long string.↵
↵
---↵
↵
### What You Need to Check↵
Given a string `s`, determine:↵
↵
Is `s` a substring of the infinite string "YesYesYes..."?↵
↵
---↵
↵
### Important Notes↵
- Case matters: "YES" is NOT the same as "Yes".↵
- The pattern strictly repeats "Yes".↵
↵
</spoiler>↵
↵
<spoiler summary="Hint">↵
↵
- Build a long enough string like "YesYesYesYes...". ↵
- Check if `s` exists inside it. ↵
- Since |s| ≤ 50, repeating "Yes" about 20 times is enough. ↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
Instead of dealing with an infinite string, we simulate it.↵
↵
#### Step-by-step:↵
1. Create a long string:↵
base = "YesYesYesYesYes..."↵
2. For each test case:↵
- Read string `s`↵
- Check if `s` is a substring of `base`↵
3. If yes, print "YES", otherwise print "NO"↵
↵
---↵
↵
### Why This Works↵
↵
Any valid substring of "YesYesYes..." must appear in a sufficiently long repetition.↵
↵
Since:↵
- Maximum |s| = 50↵
- "Yes" length = 3 ↵
↵
Repeating "Yes" around 20 times (length = 60) is enough.↵
↵
---↵
↵
### Common Mistakes↵
↵
- Using "YES" instead of "Yes"↵
- Forgetting substring must be continuous↵
- Not repeating "Yes" enough times↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
```python↵
↵
↵
def solve():↵
t = int(input())↵
↵
base = "Yes" * 20 # long enough for all cases↵
↵
for _ in range(t):↵
s = input().strip()↵
↵
print("YES" if s in base else "NO")↵
↵
↵
solve()↵
↵
↵
↵
Complexity:↵
Time: O(t × |s|)↵
Space: O(1)↵
</spoiler>↵
↵
↵
↵
## Problem-B:[problem:688129B]↵
**Tags:** `implementation` `math`<br>↵
**Difficulty:** ⭐️ (Very Easy) ↵
↵
This is a very simple counting problem.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- An integer array `a` of size `n`↵
↵
---↵
↵
#### Operation↵
You can:↵
- Pick two indices `i < j`↵
- Such that:↵
— `a[i] == a[j]`↵
— Both indices are not used before↵
↵
Each such pair gives **+1 score**.↵
↵
---↵
↵
#### Task↵
Find the **maximum score**.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint">↵
↵
- Count how many times each number appears ↵
- From each value, you can form:↵
↵
count // 2 pairs ↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We need to maximize the number of valid pairs.↵
↵
#### Key Observation↵
- Each pair needs **2 equal elements**↵
- So for a value appearing `k` times:↵
↵
number of pairs = `k // 2`↵
↵
---↵
↵
### Step-by-Step Logic↵
1. Read `n` and array `a` ↵
2. Count frequency of each number ↵
3. For each frequency:↵
- Add `count // 2` to score ↵
4. Print total score ↵
↵
---↵
↵
### Example↵
↵
Input:↵
6 ↵
1 2 3 1 2 3 ↵
↵
Frequencies:↵
1 → 2 ↵
2 → 2 ↵
3 → 2 ↵
↵
Pairs:↵
1 → 1 pair ↵
2 → 1 pair ↵
3 → 1 pair ↵
↵
Total = 3 ↵
↵
---↵
↵
### Why this works↵
Each pair uses exactly 2 equal elements, and we cannot reuse indices.↵
↵
---↵
↵
### Complexity↵
- Time: O(n) ↵
- Space: O(n) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
def solve():↵
t = int(input())↵
↵
for _ in range(t):↵
n = int(input())↵
arr = list(map(int, input().split()))↵
↵
freq = {}↵
for x in arr:↵
freq[x] = freq.get(x, 0) + 1↵
↵
score = 0↵
for count in freq.values():↵
score += count // 2↵
↵
print(score)↵
↵
↵
solve()↵
~~~~~↵
↵
</spoiler>↵
↵
↵
↵
## Problem-C:[problem:688129C]↵
**Tags:** `brute force` `implementation` `math` `sliding window`<br>↵
**Difficulty:** ⭐️⭐️ (Easy) ↵
↵
This is a parity-based selection problem that can be solved using counting and simple constraints.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- An array `a` of size `n`↵
- An integer `x`↵
↵
---↵
↵
#### Task↵
Select exactly `x` elements such that:↵
- Their sum is **odd**↵
↵
---↵
↵
#### Key Observation↵
- Sum is odd ⇔ number of odd elements selected is **odd**↵
- Even numbers do not change parity of the sum↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Count how many odd and even numbers exist.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Try to pick an odd count of odd numbers (at least 1), and fill the rest with even numbers.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Let:↵
- `o` = number of odd elements ↵
- `e` = number of even elements ↵
↵
You need to pick `k` odd numbers such that:↵
- `k` is odd ↵
- `0 ≤ k ≤ o` ↵
- `x - k ≤ e` ↵
↵
Check if such `k` exists.↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We only care about parity, not actual values.↵
↵
#### Step-by-step:↵
1. Count:↵
- `o` = number of odd elements ↵
- `e` = number of even elements ↵
2. We want to pick `x` elements with **odd sum**↵
3. That means:↵
- pick an odd number of odd elements (`k`)↵
- remaining (`x - k`) must be even elements ↵
4. Compute:↵
- `l = max(1, x - e)` → minimum odd elements needed ↵
- `r = min(x, o)` → maximum odd elements possible ↵
5. Check if there exists an **odd `k` in [l, r]**↵
↵
---↵
↵
### Why this works↵
- Odd + Odd = Even ↵
- Even + Even = Even ↵
- Odd + Even = Odd ↵
↵
So we must ensure an odd count of odd numbers is selected.↵
↵
---↵
↵
### Example↵
↵
Input:↵
n = 3, x = 3 ↵
a = [101, 102, 103] ↵
↵
Odds = 2, Evens = 1 ↵
↵
We must pick all 3:↵
- Odd count = 2 → even sum → not valid ↵
↵
Answer: No ↵
↵
---↵
↵
### Complexity↵
- Time: O(n) per test case ↵
- Space: O(1) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
t = int(input())↵
for _ in range(t):↵
n, x = map(int, input().split())↵
a = list(map(int, input().split()))↵
↵
# count odd and even numbers↵
o = sum(1 for v in a if v % 2)↵
e = n - o↵
↵
# possible range of odd numbers we can take↵
l = max(1, x - e)↵
r = min(x, o)↵
↵
# check if there exists an odd number in [l, r]↵
print("Yes" if l <= r and (l % 2 == 1 or r > l) else "No")↵
~~~~~↵
↵
</spoiler>↵
↵
## Problem-D:[problem:688129D]↵
**Tags:** `implementation` `data structures` `DP` `prefix sum`<br>↵
**Difficulty:** ⭐️⭐️⭐️ (Medium) ↵
↵
This is a classic prefix sum problem that allows answering range queries efficiently.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- A string `s` consisting of '.' and '#'↵
- `m` queries, each with `(l, r)`↵
↵
---↵
↵
#### Task↵
For each query, count how many indices `i` satisfy:↵
- `l ≤ i < r`↵
- `s[i] == s[i+1]`↵
↵
In other words, count how many **adjacent equal characters** exist in the range.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Directly checking each query will be too slow.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Precompute results using a prefix sum array.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Build an array where:↵
- `pref[i]` = number of positions `j ≤ i` such that `s[j] == s[j-1]`↵
↵
Then each query becomes:↵
- `pref[r-1] - pref[l-1]`↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We preprocess the string to answer queries in constant time.↵
↵
#### Step-by-step:↵
1. Create a prefix array `pref`↵
2. For each position `i`:↵
- If `s[i] == s[i-1]`, increment count↵
3. Store cumulative counts in `pref`↵
4. For each query `(l, r)`:↵
- Answer = `pref[r-1] - pref[l-1]`↵
↵
---↵
↵
### Why this works↵
↵
- `pref[i]` stores how many equal adjacent pairs exist up to index `i`↵
- Subtracting gives count within a range↵
↵
---↵
↵
### Example↵
↵
s = "......"↵
↵
Pairs:↵
(1,2), (2,3), (3,4), (4,5), (5,6) → all equal↵
↵
So prefix:↵
[0,1,2,3,4,5]↵
↵
Query (1,6):↵
Answer = pref[5] — pref[0] = 5↵
↵
---↵
↵
### Complexity↵
- Preprocessing: O(n) ↵
- Each query: O(1) ↵
- Total: O(n + m) ↵
- Space: O(n) ↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
s = input().strip()↵
n = len(s)↵
↵
# build prefix array↵
pref = [0] * n↵
for i in range(1, n):↵
pref[i] = pref[i-1] + (1 if s[i] == s[i-1] else 0)↵
↵
m = int(input())↵
res = []↵
↵
for _ in range(m):↵
l, r = map(int, input().split())↵
↵
# convert to 0-based and use prefix sum↵
res.append(str(pref[r-1] - pref[l-1]))↵
↵
print('\n'.join(res))↵
~~~~~↵
↵
</spoiler>↵
↵
↵
## Problem-E:[problem:688129E]↵
**Tags:** `implementation` `data structures` `prefix sum` `binary search`<br>↵
**Difficulty:** ⭐️⭐️⭐️ (Medium) ↵
↵
This is a prefix sum + difference array problem that efficiently handles range updates and queries.↵
↵
<spoiler summary="Understanding the Problem">↵
↵
#### The Goal↵
We are given:↵
- `n` ranges `[l, r]` (recipes)↵
- A threshold `k`↵
- `q` queries `[a, b]`↵
↵
---↵
↵
#### Task↵
A temperature is **admissible** if:↵
- It is covered by at least `k` ranges↵
↵
For each query `[a, b]`, count how many admissible temperatures exist in that range.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
↵
Use a difference array to efficiently count how many ranges cover each temperature.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Convert the coverage into a prefix sum array.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3 (Important)">↵
↵
Build another prefix array where:↵
- `pref[i]` = number of admissible temperatures ≤ i↵
↵
Then each query becomes:↵
- `pref[b] - pref[a-1]`↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
### Approach↵
↵
We solve this in three steps.↵
↵
---↵
↵
### Step 1: Range Frequency using Difference Array↵
- For each range `[l, r]`:↵
- `diff[l] += 1`↵
- `diff[r+1] -= 1`↵
↵
Then compute prefix sum to get:↵
- `cnt[i]` = how many ranges include temperature `i`↵
↵
---↵
↵
### Step 2: Mark Admissible Temperatures↵
- If `cnt[i] ≥ k`, then temperature `i` is valid↵
- Build a prefix array:↵
- `pref[i] = number of admissible temperatures up to i`↵
↵
---↵
↵
### Step 3: Answer Queries↵
For each query `[a, b]`:↵
- Answer = `pref[b] - pref[a-1]`↵
↵
---↵
↵
### Why this works↵
- Difference array handles range updates in O(1)↵
- Prefix sum converts it into actual frequencies↵
- Another prefix sum enables fast queries↵
↵
---↵
↵
### Complexity↵
- Building arrays: O(MAX) ↵
- Each query: O(1) ↵
- Total: O(n + q + MAX) ↵
- Space: O(MAX) ↵
↵
(MAX ≈ 200000)↵
↵
</spoiler>↵
↵
<spoiler summary="Solution (Python)">↵
↵
~~~~~↵
n, k, q = map(int, input().split())↵
↵
MAX = 200005↵
↵
# difference array↵
diff = [0] * MAX↵
for _ in range(n):↵
l, r = map(int, input().split())↵
diff[l] += 1↵
diff[r + 1] -= 1↵
↵
# build coverage count↵
cnt = [0] * MAX↵
for i in range(1, MAX):↵
cnt[i] = cnt[i-1] + diff[i]↵
↵
# build admissible prefix↵
pref = [0] * MAX↵
for i in range(1, MAX):↵
pref[i] = pref[i-1] + (1 if cnt[i] >= k else 0)↵
↵
# answer queries↵
for _ in range(q):↵
a, b = map(int, input().split())↵
print(pref[b] - pref[a-1])↵
~~~~~↵
↵
</spoiler>↵
↵
