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?
↵
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?
