311A — The Closest Pair

P.S. I feel really guilty that I've made an awful mistake on the checker.

We read the pseudo code carefully. If we ignore "break", tot will be up to .

Consider whether we can make such inequality d ≤ p[j].x - p[i].x is always false. The obvious way is to make all points' x coordinates the same. And we can just choose n distinct numbers to be all points' y coordinate.

Thus the problem is solved.

311D — Interval Cubing

Consider a number x. If we apply an assignment x = x³, x becomes x³. If we apply such assignment once more, we will get (x³)³ = x³². If we apply such assignment k times, we will get x^3k.

Thus, we can get such a sequence a₀ = x, a₁ = x³, a₂ = x³², ..., a_k = x^3k, ....

Consider a prime p. From Fermat's Little Theorem, we can get x^p - 1 = 1(mod p). Further more, we can get x^y = x^{ymod(p - 1)}(mod p), here a mod b means the remainder of a divided by b.

Fortunately, 3⁴⁸ = 1(mod (95542721 - 1)), thus, x^3k = x^3kmod48(mod p). In other words, a_k = a_k + 48, which means the cycle of the sequence is T = 48.

Let's come back to the topic. Each time we run a 1-type query, for every i in the range [l, r], we apply such an assignment a_i = a_i³. At any moment some i has been applied 48 times such assignments, we can consider this i hasn't been applied any assignments before.

We can use segment tree to solve this problem. Every node of the segment tree maintains some information: the times that we applied assignments in the node's whole range(it's a lazy tag), current sum of the node's corresponding range and the sum of the node's range after we applied assignments k(1 ≤ k < 48) times.

In such a way, we can solve the problem in O(n·T + q·T·logn) time.

If you do not realize how to maintain the segment tree clearly, you can view the code 3782263.