Arrays and simple queries| Balanced Trees
Task(hard)
Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[].
You are given M queries. Queries can be of two types, type 1 and type 2.
- Type 1 queries are represented as 1 i j : Modify the given array by removing elements from to and adding them to the front.
- Type 2 queries are represented as 2 i j : Modify the given array by removing elements from to and adding them to the back.
Your task is to simply print |A[1]-A[N]| of the resulting array after the execution of M queries followed by the resulting array.
Note While adding at back or front the order of elements is preserved.
Input Format
First line consists of two space-separated integers, and .
Second line contains integers, which represent the elements of the array.
queries follow. Each line contains a query of either type 1 or type 2 in the form
Constraints
1<=N, M<=105
1<=A[i]<=109
1<=i<=j<=N
Output Format
Print the absolute value i.e.abs(A[i] -A[N]) in the first line.
Print elements of the resulting array in the second line. Each element should be seperated by a single space.
Sample Input
8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4
Sample Output
1
2 3 6 5 7 8 4 1
SOLUTION 1
import os
import array
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n, m = [int(s) for s in input().split()]
a = array.array('i', [int(s) for s in input().split()]
for _ in range(m):
t, i, j = [int(s) for s in input().split()]
if t == 1:
a = a[i-1:j] + a[:i-1] + a[j:]
else:
a = a[:i-1] + a[j:] + a[i-1:j]
fptr.write(f'{abs(a[0] - a[-1])}\n')
fptr.write(' '.join([str(aa) for aa in a]))
fptr.write('\n')
fptr.close()
EXPLANATION STEPS
- Preprocess the Array:
- Compute a prefix sum array where prefix[i] is the sum of elements from the start of the array to index ‘i’.
- Answer Queries:
- For each query, use the prefix sum array to compute the sum in O(1) time.
