### PROBLEM LINK:

**Author:** Lalit Kundu

**Tester:** Shiplu Hawlader

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM

### PRE-REQUISITES:

Segment Trees, Number Theory

### PROBLEM:

Given a string of digits of length **N<(10 ^{5})**, do two kind of operations(total of

**M<(10**:

^{5})- Type 1:
**1 X Y**: Replace**A**by_{X}**Y**. - Type 2:
**2 C D**: Print the number of sub-strings divisible by 3 of the string denoted by**A**._{C}, A_{C+1}... A_{D}Formally, you have to print the number of pairs

**(i,j)**such that the string**A**,_{i}, A_{i+1}… A_{j}

**(C ≤ i ≤ j ≤ D)**, when considered as a decimal number, is divisible by 3.

### QUICK EXPLANATION:

Use segment trees. Store in node for each interval,

- the answer for that interval
- count1[], where count1[i] denotes number of prefixes of interval which modulo 3 give i.
- count2[], where count2[i] denotes number of suffixes of interval which modulo 3 give i.
- total, sum of interval modulo 3.

Perform merge operations in constant time.

### EXPLANATION:

We basically need to find number of subarrays in range **L** to **R** who sum is divisible by 3.

Queries are for ranges, where we have to count subarrays, we can use segment tree because we can solve our problem if we can merge two intervals and find answer for the new interval in constant time.

We can use segment tree because we can take two different subarrays and merge them in constant time to find answer for the new large subarray.

In segment tree, each subarray’s information is recursively calculated from two smaller subarrays.

While querying, we can merge different(and disjoint) subarrays to get answer for range **L** to **R**.

So, we need to design the node of our segment tree. We store in our node, the answer for current subarray. Also, we will store two arrays **count1[]** and **count2[]** as defined above.

While merging two intervals(say **node1** and **node2**), our new answer will be **node1.answer + node2.answer**, plus count of valid subarrays which start in **node1** and end in **node2**.

This pseudo code will clear the things.

```
//merges node1 and node2 and stores in node3
merge(node1, node2, node3)
//non intersecting subarrays of node1 and node2
node3.ans = node1.ans + node2.ans
for i = 0 to 2:
for j = 0 to 2:
//if adding suffix of node1 with modulo i
//to prefix of node2 with modulo j
//gives us a subarray divisible by 3
if (i + j) % 3 == 0:
//all pairs of valid indexes are valid subarrays
node3.ans += node1.count2[i] * node2.count1[j]
```

Note now, we also need to build both array **count1** and **count2** for the new interval.

Let’s build **count1** first:

Say there were **count1[i]** prefixes of node2 which when taken modulo with 3 gave **i**. Now, all such prefixes will give **(i + node1.total) % 3**, where **node1.total** denotes total sum of interval modulo 3. So, we can calculate new arrays. In similar way, we can calculate **count2**.

```
//building count1 and count2
for i=0 to 2:
node3.count1[i] = node1.count1[i] + node2.count1[3-node1.total+i]
node3.count2[i] = node2.count2[i] + node1.count2[3-node2.total+i]
```

So, complexity is: **O(N log N)** preprocessing and **O(log N)** per query.

### ALTERNATIVE SOLUTION:

Suppose we keep in segment tree for each node, how many prefix sums in this interval are divisible by 0,1,2.

For a query **[L,R]**, we just have to count number of prefix sums in interval **[L,R]** divisible by 0,1,2(let’s call them s1,s2,s3).

Our answer will be **choose(s1,2)+choose(s2,2)+choose(s3,2)**.

Why? Because, suppose **prefix_sum[i] 3 = prefix\_sum[j] 3**, then sum of substring **[i+1, j]** is divisible by 3.

For update query(mark **A[x] = y**), since we are keeping prefix sum modulo 3, for range **[x, N]**, we increase/decrease each prefix sum by **k**(k<3). We can do this using lazy propagation.