# Problem Link

**Author:** Bhuvnesh Jain

**Editorialist:** Bhuvnesh Jain

# Difficulty

MEDIUM-HARD

# Prerequisites

Masking, Fenwick trees / Segment trees, Handling updates of form nearest number in a range.

# Problem

You are given 2 string, **A** and **B**. You need to support 3 type of operations on these strings.

- 1 x y: Change the x
^{th}character in the string**A**to y. - 2 x y: Change the x
^{th}character in the string**B**to y. - 3 l r: Report the number of substrings of
**B**that have the same character set as the substring of A from index**l**to**r**i.e.**A[l:r]**.

# Explanation

Consider ALPHA = 20, the size of alphabet given the problem.

The first idea is to see that the character set of any string the problem can be represented by a mask, which can range from 1 to (2^{ALPHA}-1). Thus, we need to find the number of substrings with given mask in string B easily. For this, we fix a particular index and find the first point of occurrence of every character on the right and add the corresponding contribution to the mask. For example- In “aabbbbdac” for index 1, “a” occurs at “1”, “b” occurs at “3”, “d” occurs at “7” and “c” occurs at “9”. So the number of substrings with one endpoint at 1 and having mask 1 are 2, mask 3 is 3, mask 11 is 2 and mask 15 is 1.

Pseudo code:

```
//g[x] is the adjacency list of alphabet "x", storing positions in B where it occurs.
for(int i = 1; i <= m; ++i) {
g[b[i] - 'a'].insert(i);
}
for(int i = 1; i <= m; ++i) {
//find count of mask of all substrings which start at index "i" and update the values.
vector<pair<int,int>> events;
for(int j = 0; j < ALPHA; ++j) {
auto it = g[j].lower_bound(i);
if (it != g[j].end()) {
events.push_back({*it, j});
}
}
sort(events.begin(), events.end());
events.push_back({m, 0});
int mask = 0;
for(int j = 0; j+1 < events.size(); ++j) {
mask |= 1 << events[j].sec;
mask_cnt[mask] += events[j+1].fi - events[j].fi;
}
}
```

Once this initial computation is done, we try to handle the queries and updates. For the query on string A, we just need to find the mask of the substring A[l:r] and this requires computing if a particular character occurs in a range or not. With updates of changing a character on string A, this can be easily handled using Fenwick tree or segment tree. We just store the frequency of each character in a range and for calculating the mask, we just check if that character has a frequency greater than zero or not in the range.

To handle updates on string B, the idea is to first remove the contribution of every substring which contains the x^{th} character and then add the contribution back. For finding the number of substrings of given mask which contain the x^{th} character, we see the substring can either end at x, start at x or contain x in the middle. The first 2 are easy to calculate and are similar to the construction by finding the first occurrence to the left and right of index x. For the substring which contains x in the middle we can visualize them as 2 parts, left and right and their mask being the **OR** of the left and right mask. Thus doing this OR convolution of the left and right masks in naive manner i.e. O({ALPHA}^{2}) we can find their contribution too. For details, I recommend you to go through the nice explanation given by user meeow in this comment.

For details, refer to the setter’s solution below.

# Time Complexity

For every test case,

O(N * \log{N}) for precomputation on A.

O(M * ALPHA * \log{M}) for precomputation on B.

For query of type 1 (on A), O(\log{N}).

For query of type 2 (on B), O(ALPHA * \log{M} + ALPHA * ALPHA)

For query of type 3 (on A), O(ALPHA * \log{M}).

# Space Complexity

For every test case,

O(ALPHA * N) for string A operations

O(ALPHA * M + 2^{ALPHA}) for string B operations