Suffix problem

0

0 votes
Advanced Data Structures, Approved, Data Structures, Grammar-Verified, Hard, Ready, Recruit, Segment Trees
Problem

You are given an array A containing N integers where every integer is represented as a 23-bit binary string. You are also given the following function:

F(x,y)=Length of Longest Common Suffix of x and y

Write a program to resolve Q queries of the following types:

  • 1 x y  : Update A[x]=y
  • 2 L R x : Print sum of F(A[i],x) for LiR

Input format

  • First line: Two space-separated integers N and Q
  • Second line: N space-separated integers (denoting the array A)
  • Next Q lines: Query of either type

Output format

For each query of the second type, print the required sum.

Constraints

1N,Q105
1LRN
1A[i],x8388607

Time Limit: 6
Memory Limit: 256
Source Limit:
Explanation

410 =000 0000 0000 0000 0000 01002
510 =000 0000 0000 0000 0000 01012
610 =000 0000 0000 0000 0000 01102
110 =000 0000 0000 0000 0000 00012
310 =000 0000 0000 0000 0000 00112

For first query
F(4,1) =0
F(3,1) =1
F(5,1) =2
F(6,1) =0
F(1,1) =23
For second query F(4,4) = 23

Editor Image

?