P4585 [FJOI2015] Mars Shop Problem

On a commercial street on Mars, there are $n$ shops arranged in order by shop IDs $1 \sim n$. Among the many goods sold in the shops, each item is priced with a non-negative integer $\text{val}$. Each shop may bring in some new goods every day, and the price may be the same as existing goods. When Martians shop on this street, they usually visit all shops along a certain segment of the street, for example, the shops with IDs in the interval $[l,r]$, and choose their favorite item from them. Each Martian has different preferences. Usually, each Martian has a personal preference code $x$. For an item priced at $\text{val}$, a Martian with preference code $x$ likes it in proportion to the value of $\text{val xor }x$. That is, the larger $\text{val xor }x$ is, the more they like the item. Each Martian’s shopping card can only be used to buy goods stocked within the most recent $d$ days (including the current day) across all shops. In addition, each shop has one special item that is not restricted by the stocking date, and each Martian can choose this special item at any time. The supply of every item in each shop is guaranteed; there is no out-of-stock issue. Given events arranged in chronological order, for each shopping Martian, compute the item they like most in this shopping activity, i.e., output the maximum value of $\text{val xor }x$. The events in chronological order refer to the following two types: `0 s v`, meaning that shop $s$ stocks a new item priced at $v$ on the current day. `1 l r x d`, meaning that a Martian shops on the current day in shops with IDs in $[l,r]$, buying items stocked within $d$ days, and this Martian’s preference code is $x$.

The first line contains two positive integers $n,m$, representing the total number of shops and the total number of events. The second line contains $n$ integers; the $i$-th integer is the price of the special item in shop $i$. The next $m$ lines each describe one event. The events of each day are arranged in the order that event type $0$ comes first, then event type $1$.

For each event of type $1$, output one line with one integer representing the answer.

Constraints For $100\%$ of the data, all input integers are in the range $[0,10^5]$. Translated by ChatGPT 5