Suffix problem
Practice
0 (0 votes)
Advanced data structures
Approved
Data structures
Grammar Verified
Hard
Ready
Recruit
Segment trees
Problem
83% Success 83 Attempts 50 Points 6s Time Limit 256MB Memory 1024 KB Max Code
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 \(L \le i \le R\)
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
\(1 \le N,Q \le 10^{5}\)
\(1 \le L \le R \le N\)
\(1 \le A[i], x \le 8388607\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
1.LCMAX
Points:50
3 votes
Tags:
Data StructuresSegment TreesAdvanced Data Structures
Points:50
1 votes
Tags:
DatastructuresSegment TreesXORAdvanced Data StructuresData StructuresModular exponentiationSegment treeModulo arithmetic
Points:50
11 votes
Tags:
ApprovedData StructuresDivide-and-conquer algorithmHardOpenSegment TreesTrees
Editorial
Login to unlock the editorial