A. 没人验题.
B. 将不固定的位置从大到小排序. 没人检查checker.
C. dp.
D. 使用set和multiset维护差分集合,答案是(最大值-最小值-差分最大值),(O((n+q)log(n+q))).
E. 记有(k)个(dge b).如果(k<a),答案为(0);否则,对每个(dge b),有(1-dfrac ak)概率造成伤害,对每个(d<b),有(1-dfrac a{k+1})概率造成伤害.预处理排序和前缀和,复杂度(O((n+m)log n)).
F. (y_1)的范围为([L,R]=[lceildfrac l{x_1}
ceil,min(lfloordfrac r{x_1}
floor, m)]).存在(p|x_1,q|y_1)使得(x_2=pq),(q)的范围为([dfrac{x_1}p+1,lfloordfrac nq
floor]),同时要满足(lceildfrac Lq
ceil qle R).总共枚举(O(nlog n))次(p),每次最多枚举(O(sqrt m))个(q),因此复杂度为(O(nlog nsqrt m)).(应该有更紧的上界).
G. 考虑对每个右端点而言满足条件的左端点,对每个数字标记(区间(+1))不合法的左端点,合法的左端点值为(0).每次右端点右移只会影响到一个数字.使用线段树维护区间最小值和最小值出现次数,支持区间修改,复杂度为(O(nlog n)).