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, 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 :)
Auto comment: topic has been updated by I_Love_AnhThu (previous revision, new revision, compare).
Auto comment: topic has been updated by I_Love_AnhThu (previous revision, new revision, compare).
Problem source?
it's from Vietnamese TST 2022
do u have any idea about Segment Tree and Lazy Propagation??
no, I don't :(
Segment tree with lazy propagation?