nilsilu95's blog

Help BIT or Segment tree, print lexicographic kth smallest character

By nilsilu95, history, 10 years ago, In English 
Given a string(S) of alphabets(lower case only,a-z) of length N<(10**6), do two kind of operations(total of M<(10**5):

Type 1: 0 index c: Replace S[index] by char c.
Type 2: 1 LeftLimit RightLimit K :  Print the lexicographically Kth smallest character in the sub-string of String S starting from LeftLimit to RightLimit, inclusively.(The lexicographic order means that the words are arranged in a similar fashion as they are presumed to appear in a dictionary)

Input format:
The first line contains 2 space separated integers N and Q, denoting the length of the string and the number of operations respectively.
The next line has a string S of length N.
The next Q lines denote the update/print operations, where 0 and 1 denote the type of operation which has to happen.

Output format:
For each print operation, output the lexicographically Kth smallest character in the substring of S starting from LeftLimit to RightLimit if possible, else print "Out of range." (Without quotes)


1 <= Size of the string(N) <= 10**6
1 <= Number of queries(M) <= 10**5
1 <= LeftLimit, RightLimit, index <= N
c is a lowercase Latin letter only
1 <= K <= N
S contains only lowercase latin letters (a to z).

Sample Input
 5 3
aabbc
1 2 5 3
0 3 a
1 3 3 1


Sample Output
 b
a

Which datastructure should be used?I think BIT or segment tree should be used,but how ? How to do the lexicographically kth one?( i saw this problem while doing xseed hiring challenge at hackerearth)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1) Let's make a segment tree and in each node we will have an array of size 26, number of characters in subtree.

2) After a sum query we will get number of all characters in substring

3) We want to find k-th symbol and current is i (have[i] — number of chapter i in substring).

Find(k,i):
   If have[i]>=k return i;
   Return Find(k-have[i], i+1)
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Better use segment tree of sets with element of set as pair<character,frequency> and build can be done in nlog n and queries in log^2n and update in logn.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      May be i'm wrong but this method works for build in O(na) and query is O(na), where a is number of possible symbols. I think it's faster because set has very big constants

      → Reply