Given a constant $s$, an array of $n$ non-negative integers and you have to process $q$ queries of following types : ↵
↵
1. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] < b$ let $a[i] = s - a[i]$↵
2. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] > b$ let $a[i] = s - a[i]$↵
3. $i$ : return the current value of $a[i]$ ↵
↵
$1 \leq n, q \leq 5.10^5$↵
$1 \leq s, b \leq 10^7$↵
↵
Time limit : 2.5s↵
Memory limit : 512 mb↵
↵
I'm trying to solve the easier problem when all the updates appear before the queries, but I still can't;↵
I don't have any approach for this problem yet, can anyone give me some hints or something ?↵
Sorry for bad English :( ↵
Thanks :)
↵
1. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] < b$ let $a[i] = s - a[i]$↵
2. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] > b$ let $a[i] = s - a[i]$↵
3. $i$ : return the current value of $a[i]$ ↵
↵
$1 \leq n, q \leq 5.10^5$↵
$1 \leq s, b \leq 10^7$↵
↵
Time limit : 2.5s↵
Memory limit : 512 mb↵
↵
I'm trying to solve the easier problem when all the updates appear before the queries, but I still can't;↵
I don't have any approach for this problem yet, can anyone give me some hints or something ?↵
Sorry for bad English :( ↵
Thanks :)