Contest is not over yet !!

Actually, TL is really tight for SEGPROD, I also wrote that solution, but did many and many optimizes, also finding modular inverses in O(N + logMOD) will optimize your code nice. Check my code.

Contest is still going... (40 min left)

This is what I did.

Precomputation : For every multiple of 1000, less than 10, 000, and for every multiple of 2500 less than 100, 000, store 10 minimal Y_i.

Query : For each query, if X < 100, brute force. Now check for the highest x₁ where x₁ < X and lowest x₂ where x₂ > X for which you stored 10 minimal Y_i. Checked only for those 20(or lesser) Y_i(x).

I know it sounds silly for a 9th problem, but maybe it is tough to make a case in which this fails. Keen to know the intended solution.

I generalized convex hull trick for higher powers.

Let's call diff(x, A, B) = (a0 — b0) * x^0 + (a1 — b1) * x^1 + (a2 — b2) * x^2 + (a3 — b3) * x^3.
It's obvious, that diff has no more than 3 roots than diff(root, A, B) = 0.
Let's say than roots are R1, R2, R3.
For X < R1 diff(x, A, B) < 0 — A is better.
For R1 < X < R2 diff(x, A, B) > 0 — B is better and so on.

So what we will do: find best function for the leftmost X = MIN_X, let's call it BEST.

For each possible X we will handle list of queries and list of 'interesting' functions.
Function is interesting at XR, if it could became new best function at X = XR.

At the start we for every function F find roots of diff(x, BEST, F) — R1, R2, R3 (Ri >= MIN_X). For R1 we add F as interesting, for R2 — BEST, for R3 — F again.

Now we process all queries offline from MIN_X to MAX_X.
At every Xi we are trying to update our best function with 'interesting' functions for this Xi.
After possible update we find roots for diff(x, NEW_BEST, NOT_BEST) (Ri >= Xi) and similarly to initial actions add interesting functions to the roots.

Roots for line I found with Binary search.
For quadratic function — with formula.
For cubic — I found roots of derivative and did three BS (R < left, left < R < right, right < R)

For excluding problems with non-integer calculations I looked not only roots, but all Xs on the segment [Root — 3, Root + 3] (+-2 was not enough).

I created a comparator function for polinomials, which compares them by a₃, then a₂ and so on.

For first I precompute answer up to 320 (the constant is because 320^2 > 10^5) by brute-force.

After that I sort the queries by ascending. If for some t query (t > 320), we find a p and a q polinom, where the p polinom compares less than q polinom, and p(t) < q(t) stands, then we can remove q polinom from the set, because for every x > t, p(x) < q(x) will hold also. It can be proved indirectly, using the fact t > 320.

I'm unsure about the number of runs for a given polinomial, but it isn't too much, as I got AC in 0.26.

This is what I did.

https://www.codechef.com/viewsolution/16266475

Sort the given functions by a3,a2, and so on. Remove the useless functions, for e.g functions having the same a3,a2,a1, only one of them will always give optimal output among them, so remove them, that makes sure there are no 2 functions with same a3,a2,a1 coefficients.

Taking linear functions for example, for a given x, realize we don't need to evaluate on all functions to find the minimum value, some of them can never be optimal no matter what. For e.g. functions ax+b and cx+d. If (c-a)*x> 10^5 then lines with coefficients of x >=c will never give better solution than the line ax+b. This way we only check limited lines for all 0<=x<=10^5, and the total number of lines checked will be 10^5 * log(10^5). Similar arguement can be used for higher order polynomials to eliminate the unnecessary functions, and use brute force among the remaining lines for every x.

Works pretty fast, but I know it's far from intended, curious to know the author's solution.

SEGPROD : Chinese Remainder Theorem CSUBQ : Segment tree

you can find number of subarrays with maximum element less than equal to R and number of subarrays with maximum element less than L than take difference of both to find answer of query. To find subarrays use segment tree; https://www.codechef.com/viewsolution/16147584

SEGPROD:

Firstly, divide a_i into 2 factor, like a_i = b_i * c_i such that gcd(b_i, P) = 1. So, in each query you can calculate answer for b_i factors with modular inverse. Factorize each c_i into p_i, where p_i are prime factors of P. So, c_i = Π p_i^e_i. Now, for each query, answer for c_i factors is Π p_i^{e_l + e_l + 1 + ... + e_r} which you can handle with prefix sums on exponents of p_i's. This is O(NlogN + Q * (number - of - primes - product < P) where (number of primes product < P) can be 9 maximally since 2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 > 10⁹.

CSUBQ:

You can make segment tree with keeping answer, length of left child's answer, length of right child's answer, node index of left child's answer, node index of right child's answer. In merge function, answer for parent node will be left_ans + right_ans + left_len*rigth_len. Update lengths of childs with indexes of nodes you kept.

This is what I did:

Find the centroid of the tree and root it at the centroid, update the answer for all queries of type 2, with the best two answers that you can get, with the condition that the path must pass through the root, This can be done in O(N+Q). Then, remove the centroid, this will split the tree into parts. At this point, you can also split the queries based on which part contains the node corresponding for that query. If you do this recursively, the process will have O(LogN) levels, and at each level, the time taken to update the answers for the queries will be O(N+Q). Overall complexity is O((N+Q)*LogN)

Look at it this way: adding a bank is detaching a vertex from a tree. A query is asking for second highest number not present in the current connected component. If we process queries backwards, the adding a bank queries simplify to DSU.

Let's have a segment tree, which keeps two top values. If a vertex is a root of some set in DSU, the leaf of segment tree corresponds to the whole set. If a vertex is not a root, the leaf is empty. The segment tree is updated on union operation.

A query "max not in a set" is equivalent to max("max to the left", "max to the right") which can be answered using the segment tree.

My Approach:

Imagine if we are marking a node a bank, we are removing it from the tree. So,we have a forest now. For a node v, the only nodes which we can't reach without passing through a bank are the nodes which are in the same tree as the node v is in. We have to calculate the second largest number <= n which is not in the same tree.

Reverse the queries. Now, we are basically merging tree and maintaining the std::map of number present in the tree and the largest number not present in the tree. For merging, just merge the smaller tree in larger one at each step. When we query for a node, just iterate from the largest number not present in the tree and return the second largest number not present in it and update the largest number not present in the tree. Didn't prove why this should work in given TL but it just did.

Proof by AC, I guess