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 :(
Yeah I do, explain the sol
use a segment tree with lazy propagation to efficiently handle the range updates. For each update query, check the condition (a[i] < b or a[i] > b) within the specified range [l, r]. If the condition is met for the entire range, apply the update directly; otherwise, propagate the update to the child nodes. For point queries, ensure all pending updates for the segment containing the index are applied before returning the value.
This is too slow. Consider s=2, an array with alternating 0s and 1s, and alternating queries 1. and 2. on the whole array with b=1. In this case, each query visits all nodes, so the time complexity is O(nq), too slow.
Isn't it log n? Sorry if I'm wrong, I just learned segment trees. :)
The reason lazy segtree normally runs in O(logn) per query is that for each layer, only nodes containing the left or right edge of the updated/queried interval pass it to their children, so we have O(1) operations per layer and O(logn) layers, therefore O(logn) time per queey. However, in the solution you described, it's possible for every node (except for leaves) to pass the query to its children (see the case in previous comment). Because of that, the reasoning above doesn't work, all nodes may be visited during one query, and resulting time complexity may be O(nq) for some cases.
as MathGuy pointed this out, it may need to do all (r — l + 1) operations. and bro, this is a team selection test problem, it's cf rating would average around 2900. I don't think it to be like: use segment with lazy and it's solved
Segment tree with lazy propagation?
There is a solution of $$$O(n\sqrt{n}\log{n})$$$,but it is not fast enough.
What's the point of saying there is a solution without saying the solution, even if it isn't fast enough, but still better than plain $$$n^2$$$, just say it, someone will learn from it, and even better, someone might be able to optimize to like $$$n(\sqrt n + log{(n)})$$$ which is $$$n\sqrt n$$$ which is AC if coded efficiently. (this happened at my class last week).
I have come up with an O(nlog^2(n)) solution. s-(s-a[i]) = a[i] => there are only two possible values of a[i], which are defined by initial value of a[i], they are a[i] and s-a[i]. Let x = a[i] and y = s-a[i]. Assume x <= y (otherwise we can let y = a[i] and x = s-a[i] and do one operation on a[i], so that it will hold true). Firstly, let's do b-=1 for the first type of operation and b+=1 for the second, so that conditions will be a[i]<=b and b>=a[i]. To find a current value of a[i], we must know three things: 1) Type and time of the last operation with l <= i and i <= r and x <= b <= y, let's denote its time by T. 2) Number of operations of the first type with l <= i and i <= r and y <= b with time greater than T. 3) Number of operations of the second type with l <= i and i <= r and b <= x with time greater than T. To solve the first task, we can maintain a segment tree of segment trees with maximum on interval. Second and third tasks are similar and in both we can maintain a segment tree of persistent segment trees with sum on interval. Since queries are known beforehand, we can compress segment trees.