给定一个长度为$n$的数组，这么定义该数组的哈希值：每次从数组开头取出两个数，将后一个数减去前一个数得到的数值放入数组开头，如此重复，直到数组中只剩下一个数，最后这个数便为数组的哈希值。现在每次操作把一段区间的数加上$v$，要求输出每次操作后数组的哈希值

显然数组的哈希值为$\sum_{i=1}^n{\left(-1\right)^\left(n-i\right)\times a_i}$

因此当区间左右端点奇偶性相同时对哈希值无贡献，奇偶性不同时如果区间左端点与$n$奇偶性相同则哈希值加$v$，否则减$v$

时间复杂度$O\left(n\right)$

在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n+1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n+1\right)}{2}\right)$

大概思路为二分答案$d$，统计哈密顿距离$\le d$的点对个数

首先，将坐标系顺时针旋转$45$度，放大$\sqrt{2}$倍，所以所有点坐标变为$\left(x-y,x+y\right)$，与某个点哈密顿距离$\le d$转化为在以该点为中心的边与坐标轴平行且长度为$2d$的正方形中

考虑用滑动窗口+树状树组统计答案，具体过程见代码

<code cpp> a <\code>