All Tracks>Data Structures> Arrays> 1-D> Problem
Make an array
★★★★★

0

0 votes
Arrays, Data Structures, Prefix, 1-D
Problem

You are initially given an array A of length N and Q queries. Each Queries are either of 2 types :

type 1 : 1 L R V : add V to all the numbers in the range L to R which are not divisible by 2.

type 2 : 2 L R V : add V to all the numbers in the range L to R which are divisible by 2.

Print array A after all Q queries.

Input :

  • First line of input consists of 2 integers , N and Q, length of array and number of queries respectively.
  • Second line contains N space separated integers denoting elements of array.
  • Each of the following Q lines contains queries.

Output :

  • Output space separated elements of array after applying all the queries in single line.

Constraints :

  • 1≤N,Q≤105
  • 1≤L,R≤N
  • 1≤Ai,V≤109
  • Vmod2=0
Sample Input
5 2
1 2 3 4 5
1 1 5 2
2 2 3 2
Sample Output
3 4 5 4 7
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

for first query : 1 1 5 2 

query is of type 1 .so, all the numbers not divisible by 2 in range 1 to 5 are incremented by 2 . 

now array A becomes : [3 2 5 4 7]

for second query : 2 2 3 2

query is of type 2 .so , all the numbers divisible by 2 in range 2 to 3 are incremented by 2.

so , array becomes : [3 4 5 4 7]

Contributers:
Editor Image

?