Range Minimum Queries
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an array of N integers. You should support the following queries on this array.
- 0 L R : Find the minimum integer in the range AL, AL+1, ..., AR.
- 1 L R X : You should apply the assignment A[i] = A[i] & X, for all indices i in range [L, R], where & denotes bitwise AND operation.
First line of the input contains two space separated integers N and Q.
Second line contains N integer numbers denoting array A.
In the next Q lines, each contain one of the queries described above.
For each query of the type 0, output a single line containing the answer of the query.
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai, X ≤ 109
- 1 ≤ L ≤ R ≤ N
Input: 5 5 1 5 2 3 4 0 2 5 1 1 5 6 0 2 2 1 2 5 3 0 1 3 Output: 2 4 0
|Tags||bitwise-operatn, cook71, kingofnumbers, medium, segment-tree|
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.