ynoi2018专题

P4117 [Ynoi2018] 五彩斑斓的世界

分析第一个操作 朴素的做法,遍历一遍大于x就-=x,极限复杂度O(mn) 分块做法 整块:我们维护一个最大值,从mx到x遍历一遍(减去x)用并查集操作merge(i,i-x),考虑mx=100001,x=1,极限复杂度O(mV) 我们可以分析 1.x>(mx/2),从mx到x遍历一遍,应该是最优的复杂度O(mx-x) 2.x<(mx/2),最优的复杂度应该是O(x),因此思考在这种

[Ynoi2018]天降之物

天降之物 题解 只有 ** 出题人才会出这种又难调又卡常的 ** 题。 笔者原先很快奶出了一个 O ( n n log ⁡   n ) O\left(n\sqrt{n}\log\,n\right) O(nn ​logn)的做法,然后调了一个下午,交上去后死活过不了,只好又优化了半天优化出了一个 O ( n n ) O\left(n\sqrt{n}\right) O(nn ​),又调了

bzoj 5143 [Ynoi2018]五彩斑斓的世界

二阶堂真红给了你一个长为n的序列a,有m次操作        1.把区间[l,r]中大于x的数减去x        2.查询区间[l,r]中x的出现次数        题解:        今天模拟赛第一题=_=,把题看错,然后暴力打了30分跑路了。        由乃题肯定是分块了。        由于数字的大小只有十万,可以先假装