Given a constant $$$s$$$, an array of $$$n$$$ non-negative integers and you have to process $$$q$$$ queries of following types :
- $$$l \ r \ b$$$ : for each $$$i$$$ in range $$$[l, r]$$$, if $$$a[i] < b$$$ let $$$a[i] = s - a[i]$$$
- $$$l \ r \ b$$$ : for each $$$i$$$ in range $$$[l, r]$$$, if $$$a[i] > b$$$ let $$$a[i] = s - a[i]$$$
- $$$i$$$ : return the current value of $$$a[i]$$$
$$$1 \leq n, q \leq 5.10^5$$$ $$$1 \leq s \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 :)