Chef & Chutneys
Tag(s):

## Advanced Data Structures, Data Structures, Gaussian Elimination, Linear Algebra, Math, Segment Trees

Problem
Editorial
Analytics

A chef has recently opened a new restaurant to serve his special dishes. He has a list of ingredients from which he makes them. Each ingredient is denoted by a unique lowercase letter. Thus, a dish is represented as a string of ingredients possibly with repititions. There are $N$ people in his restaurant currently each of whom have ordered some dished.

You are given a collection of dishes with duplicates possibly. The chef can serve one of his favorite dishes from them if he is able to reorder all their ingredients (i.e. a permutation of the concatenation of all the strings) such that they form a palindrome. You have to facilitate the day-to-day working of the restaurant. There are two types of events happening in the restaurant:

1. A person updates his order to get a new kind of dish.
2. People in the range $[L, R]$ wants to know the number of non-empty subsets of $A[L \ldots R]$ from which the Chef can make one of his favorite dish.

You are given the initial orders of the people. Therefore, you have to process $Q$ events of the mentioned types.

Input format

• First Line: Two integers $N, Q$ denoting the number of people currently in the restaurant and the numbers events happening over time

• Second Line: $N$ space seperated strings consisting only of lowercase letters, $A_1, A_2, A_3,\ldots, A_N$ where $A_i$ denotes the chutney initially ordered by the $i^{th}$ person
• Next $Q$ Lines: Event of any of the above two type in the following format:
1. $1 \text{ } i \text{ } X$: The $i^{th}$ person has updated his order to a new chutney $X$: $A[i] = X$
2. $2 \text{ } L \text{ } R$: Count the number of subsets satisfying the constraint described above.

Output format

Print the required answer for each event of the $2^{nd}$ type.

Constraints

$1 \le N \le 2\cdot10^5$

$1 \le i \le N, 1 \le L \le R \le N$

$1 \le Q \le 5 \cdot 10^4$

$1 \le \sum |A_i|, \sum |X| \le 10^6$

There is at least one event of $2^{nd}$ type.

SAMPLE INPUT
11 8
tamarind red mint coconut ginger peanut pudina tomato periperisauce hummus redchilli
2 1 4
2 3 10
2 1 7
2 4 11
1 8 papaya
2 4 11
1 4 onion
2 1 7
SAMPLE OUTPUT
1
0
2
2
2
3
Explanation

For the first 3 events, answers are as follows:

1. We have only 1 subset from the first 4 chutneys from which Chef can prepare one of his favorite chutney: $\{ \text{tamarind}, \text{red}, \text{mint} \} \Rightarrow \text{tamrindednirmat}$.
Note: There might by many possible favorite chutneys Chef can prepare from a specific collection of chutneys but people are only interested to know if he can prepare one of them.
2. There is no subset from $A[3 \ldots10]$ from which Chef can prepare any of his favorite chutney.
3. Indices from which favorite chutney can be prepared: $\{1, 2, 3\}, \{1, 3, 4, 5, 6, 7\}$.
Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Circuits '20

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Number Theory
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Data Structures > Arrays