Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subarray Replacement

By Ahasan_1999 · Limits 4s, 256 MB

You are one of the greatest programmers of the decade. Ahasan heard that you can solve range query problems in a minute. He came to you with the following problem.

Given two arrays AA and BB both of NN integers, your will process QQ queries of the following 33 types:

  1. Find the maximum value in the range [L,R][L,R] in array AA

  2. Update A[I]A[I] with XX

  3. Replace the subarray A[L1R1]A[L_1… R_1] with subarray B[L2R2]B[L_2… R_2]. That means set A[L1]=B[L2],A[L1+1]=B[L2+1],A[L1+2]=B[L2+2],...,A[R1]=B[R2]A[L_1]=B[L_2], A[L_1+1]=B[L_2+1], A[L_1+2]=B[L_2+2],..., A[R_1]=B[R_2].

Input

The first line contains two integers N(1N106)N (1\leq N\leq 10^6) and Q(1Q106)Q (1\leq Q\leq 10^6), the number of elements in the arrays and the number of queries respectively.

The second line contains NN integers A1,A2,,AN(1Ai109)A_1, A_2, …,A_N (1\leq A_i\leq 10^9), the elements of the array AA.

The third line contains NN integers B1,B2,,BN(1Bi109)B_1, B_2, …, B_N (1\leq B_i\leq 10^9), the elements of the array BB.

The next QQ lines describe the queries. Each line contains a query in the following form:

  • 1 L R1\ L\ R - find the maximum value in the range [L,R][L, R] (1LRN)(1\leq L\leq R\leq N) in array AA

  • 2 I X2\ I\ X - update A[I]A[I],(1IN),(1\leq I\leq N) with X(1X109)X (1\leq X\leq 10^9)

  • 3 L1 R1 L2 R23\ L_1\ R_1\ L_2\ R_2 - replace the subarray A[L1R1]A[L_1…R_1] with subarray B[L2R2]B[L_2…R_2], where (1L1R1N),(1L2R2N)(1\leq L_1\leq R_1\leq N), (1\leq L_2\leq R_2\leq N) and (R1L1+1=R2L2+1)(R_1-L_1+1=R_2-L_2+1)

Output

Print the output of each query of type 11.

Sample

InputOutput
6 5
3 7 9 2 4 1
9 2 5 6 1 5
1 2 5
3 1 4 3 6
1 2 5
2 2 4
1 1 6
9
6
5

    Discussion

    Statistics


    100% Solution Ratio

    YouKnowWhoEarliest, 1M ago

    Deshi_TouristFastest, 2.1s

    YouKnowWhoLightest, 106 MB

    Deshi_TouristShortest, 2357B

    Submit

    Login to submit