Блог пользователя jhjfbsbfkbjfnfnfjfj

Автор jhjfbsbfkbjfnfnfjfj, история, 4 года назад, По-английски

Hello everyone! How can I do this question using segment trees? what type of array to create? https://codeforces.com/problemset/problem/1234/D

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For solving this question with segment tree, you can have an array(say M) of size 26 in every node of segment tree. Suppose a particular node of segment tree hits the interval [L,R], the array value M[i] in that node stores the number of occurance of ith(i=char-'a') character in the range [L,R]. We can combine any two nodes simply by adding the number of the number of occurances in the two nodes. we can update also in the similar fashion. For answering queries you can get a combined node of all the ranges hit by query range in segmnet tree and then count the number of non zero value in the combined node.

There is another way to have a bool array in everynode rather that count array and then for paticular range, M[i] will be true if ith character is present in that range. Combination of two nodes will be simply 'or' operation on the corresponding nodes. At the end we can count the number of true values in the combined node formed after querying segtree.