这篇文章受密码保护，输入密码才能阅读

题面 第一反应断环为链, 转化为均分纸牌, 但复杂度为$ O(N^2)$根本不对. 实际上这道题比均分纸牌只多了1与n之间的转移, 设 n给1 $ x_n$个糖果, i给i+1 $ x_i$个糖果, 则有: $$\left\{ \begin{array}{ll} a_1+x_n-x_1=av \\ a_2+x_1-x_2=av \\ a_i+x_{…

题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分别开一个大根堆left 小根堆right, 那么right.top()即为中位数. 每次加入一个数x, 若比当…