Given an array A of size n (n<=150000) and a permutation P. You must do q queries(q<=150000) of 4 types:
1 l r v: A[p[i]]+=v with all l<=i<=r
2 l r: calculate sum of all A[i] with all l<=i<=r
3 x y: swap P[x] and P[y]
4 k: roll back A and P to right before the kth query
Here's the link the the original problem(Vietnamese) if you're interested: https://oj.vnoi.info/problem/olp_sc23_pquery
I'll be looking forward to your answers. Thank you :D
Edit: Apparently someone's accepted solution has square root decomposion as a part of it but I don't have access to their code and any detail on how it works. Can someone expand on this approach?
Auto comment: topic has been updated by PUSSY_LICKING_LOLI_69 (previous revision, new revision, compare).
It's not every day that you come across a PUSSY_LICKING_LOLI_69 solving segment tree problems; What a time to be alive! In any case, here's how I would solve it:
Type $$$1$$$ and $$$2$$$ can be handled by a standard lazy segtree.
Type $$$3$$$ can be handled by querying $$$p_x$$$ and $$$p_y$$$, then adding $$$p_y-p_x$$$ to $$$p_x$$$ and $$$p_x-p_y$$$ to $$$p_y$$$.
Type $$$4$$$ can be handled by making the segtree persistent (see tutorial).
How do you do type 1 query using lazy segtree? Note that it is
A[P[i]] += v, notA[i] += v.Oh shoot, misread it; this won't work then
might or might not change my handle this Christmas. Haven't thought of one yet :D
you sure about the type 1 query?
nice pfp lmao
A rather inefficient approach to show that it can be done in polylogarithmic time: Take the inverse of the permutation; then the first query becomes doing A[i] += v for l <= P^-1[i] <= r. Then this becomes maintaining a set of points $$$(i,P^{-1}[i])$$$ which can be done with a 2D segment tree.
I looked at the problem and it doesn't seem to require you to do it online, so you can take it offline and the 4th operation becomes reverting operations -- both operations have easy inverses.
What is the time complexity for your approach? Can a 2D segtree handle a (1e5 X 1e5) board, or do we have to make it both dynamic and persistent? Seems like a lot of work...
Auto comment: topic has been updated by PUSSY_LICKING_LOLI_69 (previous revision, new revision, compare).