Problem link:-https://www.codechef.com/problems/QPALIN
How to use segtree in such questions…I have done practice of some questions(basic) using segtree?
here comes string.
You can solve it by segment tree or BIT.
Here’s my solution using BIT > link text
Solution
We need to find number of odd characters in interval l to r. If it is less than 2 then answer will be YES else NO.
So we need to maintain a frequency array for each alphabet in the range 1 to n. Answer each query in logn complexity which can be done using BIT/segment tree.
If you are concerned just about how to handle string, then you can replace them with their ASCII number.
Following observations are sufficient to solve this problem
-
if the string has even length it can be palindrome iff all the characters have even frequency of occurrence
-
if the string has odd length it can be palindrome iff exactly one character has odd frequency of occurrence
BIT works faster than Segment-Tree, but not asymptotically. So if you already know BIT then you should see dushsingh1995 solution. Otherwise, here is one Segment-Tree based solution for you Solution
EDIT : you can further reduce these observations to one pointed out by dushsingh1995
I just looked at its editorial and found a very interesting optimization. We can solve it without creating hash tables or 26-length array in each node. We will use a very beautiful property of XOR operation, which is, XORing same number even number of times cancels out.
For, e.g, 2 ^ 3 ^ 1 ^ 2 = 1 ^ 3
Thus only those terms gets XORed which appear odd number of times, we can use this to our advantage.
Since we are using 26 character in our string, each character can be thought as integer whose only ith bit is set to 1 and i = ASCII(character) - 97. Thus we would be needing at most 26 bits, and thus normal “int” would suffice for our purpose. For merging two nodes, just XOR the numbers, and finally check the number of bits set to 1.
If you are still confused, then look at this, almost same as the previous one. Solution
1 Like