There are n distinct integers. a1, a2, ..., an (1 <= n <= 1e5) a1 < a2 < ... < an (1 <= ai <= 1e5) And there is an integer k (k <= 1e5) I will choose n integers. b1, b2, ..., bn, ai <= bi <= k for i = 1, 2, ..., n For each choosing method, there is a product, the product of the factorial of each number's occurence. I want to calculate the sum of these products.

For example:

n == 3

k == 4

[1, 3, 4]

Then, the answer is 18.

I don't know how to solve it.

contest link I got a TLE in G of this contest.

Let me brief you on the question.

There is an array a with a length n(2 <= n <= 1e5)(1 <= ai <= n) There are T queries(1 <= T <= 1e5) For every query, there are four integers l, r, p, q(1 <= l <= r <= n, 1 <= p < q <= n) Then, change the array. Keep the elements equal to p and q. Remove other elements. Output the inverse number of the array after changing. After every query, the array becomes to the initial one.

I came up with a divide and conquer algorithm.

Let me describe my solution.282174326

The key point lies in how to get the answer of the big problem(the range of [l, r]) after getting the answer of the small problem(the range of [l, (l + r) / 2] and the range of [(l + r) / 2 + 1, r]).

The inverse number of range[l, r] equals to the inverse number of range[l, (l + r) / 2] plus the inverse number of range[(l + r) / 2 + 1, r] plus the amount of q in range[l, (l + r) / 2] multiply the amount of p in range[(l + r) / 2 + 1, r], because p < q.

I can get the amount of an element x in range[l, r] in O(logn) using binary search.

Of course, I need to get the ID vector for each element before all the queries.

I have been devoting into competitive programming since the beginning of this year. In the first 3 months, I learned several basic algorithm in CP (of course, I solved so many questions during this period). Later, I heard that a website named "codeforces" is very good for CPer, so I registered this account. To be honest, my programming skill improved a lot during last several months. However, I feel that it's difficult for me to improve my rating now. I have been cyan color for about 50 days and it's hard for me to become blue color. Actually, I practiced very hard during this summer vacation, but my rating improvement didn't achieve my expectancy. Yesterday, I took part in Codeforces Round 972 and I haven't got enough time to solve 2005C - Lazy Narek, although I came up with it (I failed to finish my code in last 40 minutes in the contest). I really want to participate in ICPC on behalf of BUPT next year, and I know that there is a long way to go for me. I have to improve my rating. How can I do it more quickly?