I am attaching a picture about the question. Kindly refer to the picture.

# | User | Rating |
---|---|---|

1 | tourist | 3533 |

2 | Um_nik | 3459 |

3 | maroonrk | 3394 |

4 | ksun48 | 3384 |

5 | ecnerwala | 3347 |

6 | Benq | 3301 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3288 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 206 |

2 | Monogon | 196 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Um_nik | 182 |

7 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 168 |

I am attaching a picture about the question. Kindly refer to the picture.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2020 09:59:39 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Sample test cases?

You didn't tell us whether the test is finished or not. We shouldn't help you if the test is not finished yet.

It's finished bro.

Reverse all strings, so task becomes about prefix instead of suffix. Create segment tree, where each node have a trie that contains all strings from this node's corresponding segment (each string will be in $$$log~n$$$ tries, so memory will be $$$23 \cdot n~log~n$$$). With trie it's easy to count necessary sum of all string nested in this trie in $$$O(23)$$$, so overall query's complexity will be $$$O(23 \cdot log~n)$$$.

You can do it with a single trie

can you please explain

Basically what you and lemelisk said in the comment below, I'm not sure if it's better, just seems slightly easier to implement

create a trie with reversed strings and store indices of strings in each node in sorted order then query for reversed string, you can find out for each each prefix of reversed string how many strings from given range match this prefix

For updates you will need to store indices in BSTs that supports query "how many elements is smaller than given value". But that a nice alternative to segment tree's solution and it even has lower memory consumption complexity.

I solved it using map and policy based data structure My solution

map of ordered set!!nice