first question
given an array a[] of size n and we are asked q queries and there will be 3 types of queries
1 l r for each i in l <= i <= r ai = ai/d where d is the smallest prime factor of ai
2 l r print the sum of all ai with l <= i <= r
3 i k set ai = k
constraints:
1 <= n <= 2e5
1 <= q <= 1e5
1 <= ai , k <= 1e6
sample test case:
5 3
10 2 8 7 6
2 1 4
1 1 4
2 1 4
second ques:
I have attached the images of the second ques
In Q1, first query doesn't make any sense, can you recheck once, i believe there is a typo?
yeah! sorry actually there was a typo. I have updated it
Q1 seems to be classic segment tree problem. You can precompute prime factors and then it's just range / point update and range query
Dunno why you got downvoted, seems right to me
Q1: any ai <= 1e6 can have at most 7 prime factors. So you can manually iterate and divide them (you'll need a seg_tree of course, to answer type 2 queries). Type 3 ops doesn't cause problems cuz they are point update ops and for each such update you'll have to divide it by 7 more times. You can see that each cell in the array will be visited not more than 7*(no. of type 3 queries + 1). Q2: Binary lifting + binary search.
You don't need anything fancy for Q1, you could have around 20 prime factors on each Ai since 2^20 ~ 1e6. As you said, keep 1 multiset (or set of indexes) with each value greater than 1 on the range, then update each element one by one. Note that op.1 doesn't affect Ai = 1, so just keep track of how many 1's there are in total and the update the sum at each step.
yeah got it can you also provide the solution for the second ques
Simulate the proccess with a sparse table, if you "jump" 2^k nodes up and it's used try 2^(k-1) instead, if it's not, keep jumping up and so on.
How do you handle the 3rd op?
Add the index again to the set if it became 1 and now changed with the update. Worst case, that number will take 20 steps to be 1 again, so it's still fast.
Ohh got it thnx, I was confused it might TLE.
In first problem, any element will become 1 after 15-20 operations, so, just do brute force, put all indices from 0 to n — 1 in a set, for update query traverse all indices in the range and do the operation, if some element becomes 1 then remove from set, and put the updated values in segtree, number of updates is bounded overall, for sum query the segtree, 3rd is just adding index back to set if it's not 1 and update segtree.