【题解】HNOI2017 简要题解

D1

~~面对数据编程情况下 270~~

单旋(树状数组)

发现每次splay的东西的都是最值。以最小值x伸展到根来举例，这也就意味着rotate的时候一直没得左子树，那么原树的改动是

(fa[x])和(rs[1][x]) 连边
除了(rs[1][x])中的点，其他点深度++

其他操作也是一样的。

联系BST (T)的性质，变化相同的点构成连续的区间，比如(rs[1][x])中的点就是区间((x,fa[x])cap T)，其实这个(cap)不用管他，因为插入的时候清空就行了。

那么维护每个点的fa和son，以及支持区间加单点查询的树状数组就完事了

影魔(离线询问枚举端点)

还是树状数组(滑稽)

考虑第二档分是什么意思，(2p_2=p_1)，就相当于"确定一个位置(i)，再确定一段(i)为端点的开区间，这个区间里最大值是(c)，如果(c<p[i])就对答案+=(p_2)"。那么每个点维护一个(P_i,N_i)分别表示上一个/下一个比他大数的位置，离线枚举一次左端点枚举一次右端点随便做做就行了。

具体方法是维护一个队列一个树状数组，对于没有越过(N)的数(i)存到队列中，那么每个询问在这个队列里找到最后一个位置(le r)的下标，然后贡献是下标( imes)区间长度。然后对于越过的情况，加到树状数组里。每次询问的时候也要查询一下，注意这只统计了(i)作为右端点的情况，所以要枚举两次。

受到这档分的启发，考虑一个这样的办法，先假装(p_1=2p_2)，做一边上述算法，然后令(p_1=p_1-2p_2)，现在就是要数这个东西了。其实，假设现在枚举到左端点(l)，然后对于一个点(x>l)，我们实际上就是要查询(# iin[l,x),N_i<x)，又是一个经典的二维偏序问题，也是离线枚举一次右端点一次左端点就行了，具体操作同上，只是我们维护值域。

然后这个方法有点复杂，洛谷第一篇题解对询问进行二位数点的高明多了。

礼物(FFT)

妈的我是sb

70pts做法

枚举一下平移的长度，然后得到(z_i=x_i-y_i)，这个情况的答案是(sum (z_i+c))，化简就是(sum z_i^2+2csum z +nc^2)，令(c={-2sum zover n})取最近那个整数

正解：FFT

不想写了，经典做法，我是sb

要上课了咕咕咕