ICL1803 - Editorial

Problem Link

Practice

Contest

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 xth character in the string A to y.
  • 2 x y: Change the xth 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

Solution Links

Setter’s solution