Array and queries

5

6 votes
Medium, Ad-Hoc, Lazy Propagation in Interval/Segment Trees, Advanced Data Structures, Data Structures, 普通
Problem

Given an array a of size \(2^n\) indexed from 0 to \(2^n - 1\) and q queries of type:

  • \(1 \; l \; r\) (\(0 \le l \le r < 2^n\)): Print \(\max(a_l, a_{l+1}, \dots , a_r)\).

  • \(2 \; l \; r \; v\) (\(0 \le l \le r < 2^n, 0 \le v \le 10^9\)): Assign value v to every \(a_i\) (\(l \le i \le r\)).

  • \(3 \; k\) (\(0 \le k < 2^n\)): Permute array a by permutation p, \(p_i = i \; XOR \; k\). Because \(0 \le k < 2^n\) it can be proved that p is a permutation.

If we permute array s by permutation p then the resulting array v will satisfy the condition that \(v_{p_i} = s_i\).

\(\textbf{Input}\)

The first line contains numbers n (\(0 \le n \le 18\)) and q (\(1 \le q \le 2^{18}\)).

The second line contains \(2^n\) numbers - \(a_0, a_1, \dots , a_{2^n - 1}\) (\(0 \le a_i \le 10^9\)) separated by space.

Each of the next q lines contains one type of query from the above mentioned types of queries.

\(\textbf{Output}\)

For each query of first type, output a line containing the answer in chronological order.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For first query the answer is \(\max(1,2,3) = 3\).

After the second query the array is \((0,1,1,1)\).

After third query the array is \((1,0,1,1)\).

At fourth query the answer is \(\max(0,1) = 1\).

At fifth query the answer is \(\max(1,0,1) = 1\).

Editor Image

?