Interactive
Alex_KPR: — ...beginning somewhere from treaps, FFT and so on, coding and debuggig become straining and boring tasks...
Kunyavsky: — May I nitpick? Why are writing of Decarte's tree and FFT in same timescale?
Alex_KPR: — That's the rst thing I remembered with high requirements of time and big space for mistakes.
Kunyavsky: — I've said: I'm nitpicking. On my opinion, here are two things, one of which is incredibly easier to code.
homo_sapiens: — Absolutely agree. FFT is written two or even three times faster than treap (but it's usually pushed with hands and feet)
Kunyavsky: — I meant quite the opposite. At the end, very speci c topic that is.
homo_sapiens: — Seems really a matter of taste...
Time to nd out, what's simpler.
Two sequences of N integers are o ered: {x_i} and {y_i}.
If you like FFT more, imagine these are coecients of two polynomials:
Find coecients of polynomial P(z)·Q(z).
Though, if you like treaps more, imagine that {x_i} are keys, and {y_i} are priorities. Build treap by inserting into it all N elements (x_i, y_i). coherently. Output height of resulting treap after each insertion.
Those who chose FFT, recollect, that treap is binary search tree by keys, contained in (x_i). And in the same time it's a heap by priorities in nodes (y_i). I.e. for each vertex of the tree all the nodes from left subtree have lesser keys, than in top, and all vertices of right subtree have greater keys. And also priorities of sons are lesser than priority of top.
ndependently of what you've chosen, author urges not to use prewritten code for this problem.
Input
The rst line contains number N. The second has N di erent integers — {x_i}. The third line has N di erent integers, which make consequence {y_i}.
Output
If you chose FFT, display 2N-1 integers, which are coecients of resulting polynomial. If treap, then N integers are heights of tree after insertion of each vertex.
Actually, you can display both, but then both results will be checked for correctness.
Limits
1 ≤ N ≤ 50000
1 ≤ x_i ≤ 50000
1 ≤ y_i ≤ 50000
guaranteed, that height won't be greater than 50.