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?