E

一道感觉非常巧妙的二分。

可以将每种商品分开来看：第\(k\)次买商品\(P_i\)时，价格为\((2k-1)P_i\)。

这样，就将每种商品拆分为了多个实体的商品，并有自己的价格。想最大化购买物品的总数，一定是每次购买时贪心选择当前所有物品中最便宜的那个。

但模拟一定会\(TLE\)，可以枚举购买过程中买的最贵的一件商品，设其价格为\(x\)。

这样的话，价格\(<=x\)的所有商品均一定会被购买，而此时可能会剩下一些钱，可以去购买价格\(>x\)的物品。显然\(x\)是具有单调性的，故每次可以二分\(x\)，看将所有\(<=x\)的商品购买完后，是否可以购买完价格为\(x+1\)的商品。

若能买完，则真实值一定比\(x\)要大（至少是\(x+1\)），扩大左边界；若\(<=x\)的物品不能全部买完，则真实值一定比\(x\)要小，缩小右边界；否则真实值就是\(x\)。

注意二分边界要足够大，因为可以购买的最大价格不止是原商品的最大价格，容易遗忘！

code

F

考虑对每一个\(X\)计算答案。初始时没有经过任何区间，答案为\([1,2,3,...,5e5]\)。

枚举要经历的区间，由于每经过一个区间\([l,r]\)，值位于\([l,r]\)内的\(X\)会加\(1\)，则在经历任意一个区间后，可以保证答案序列的非递减性。

因为对于任意\(X_i<X_j\)，在\(X_i\)不断递增的过程中，由于每一次只会加\(1\)，故递增时不会突然发生\(X_i>X_j\)的情况，最多只会等于\(X_j\)，那么以后二者的变化就会永远相同，不会发生突变的情况。

所以每经历一场比赛，会增加的\(X\)在答案序列中一定也会呈现为一个区间的形式，这样就相当于区间加，可以用线段树二分来找要加的区间的左右端点，最后回答每个询问即可。复杂度\(O(nlog^{2}X + QlogX)\)

code