<> &nbs; &nbs; &nbs; 我们学会了快速傅立叶变换，狄利克雷卷积现在我们来解决一下快速沃尔什变换。 <> &nbs; &nbs; &nbs; 我们来模仿一下解决多项式乘法的过程我们先是把原数组做一次傅立叶变换，然后再相乘最后再做一次逆变换。 <> &nbs; &nbs; &nbs; 显然是可以嘚：我们设一个数组它表示A数组FWT变换之后的结果。 <> &nbs; &nbs; &nbs; &nbs;其中+表示按位相加二元组表示前后相接，也就是说其中01表示二进制下标的第一位恰好分为两部分。 <> &nbs; &nbs; &nbs; &nbs;首先来看，明显的当我们把A,B拆开时贡献到的只有，而贡献到的就是也就是说。（因为是或运算啊 <> &nbs; &nbs; &nbs; 为什么可以拆洇为考虑每个多个数组 加起来和分开 并不影响 每个位置上面的数对后面的影响，具体可以试一下手算
&nbs;&nbs; &nbs; &nbs;再看，这个按位相乘又等于什么呢相当于前面和前面的相乘，后面的和后面的相乘 <> &nbs; &nbs; &nbs; 这个是非常明显的，因为当只有一个数的时候所以两个数相乘就相当于贡献到唯一嘚C位置。 <> &nbs; &nbs; &nbs; &nbs;把上面的四条式子换到上面的式子中可以发现上面所化简的，是相等的 <> &nbs; &nbs; &nbs; &nbs; 考虑我们怎么从A变为的，是不是先从小的开始然后將左边的值加到右边。 <> &nbs; &nbs; &nbs;最后求逆的证明有的博客写得很复杂，其实根本不需要就相当于将加的减回去即可。

<> 小a有一个长度为n的排列。定义一段区间是"萌"的当且仅当把区间中各个数排序后相邻元素的差为1
现在他想知道包含数x,y的长度最小的"萌"区间的左右端点 <> 也就是说，我们需要找到长度最小的区间[l,r]满足区间[l,r]是"萌"的，且同时包含数x和数y <> 如果有多个合法的區间输出左端点最靠左的方案。 <> 第一行三个整数N,x,y分别表示序列长度询问的两个数
第二行有n个整数表示序列内的元素，保证输入为一个排列
输出两个整数表示长度最小"萌"区间的左右端点
<> &nbs;&nbs;&nbs;&nbs;&nbs;&nbs;先求数组的区间最大值和最小是，而且容易看出要找出合法的区间必定max-min=r-l那么将数列按照值排下序，在求新数组的区间最大值和区间最小值那么从原始区间[ l, r ]，如果区间中max-min>r-l那么必定有其他数在外面，然后利用第二个数组找出[min,max]之间id的最大最小值那么就是位置不在[l,r]里面，但值却在区间最大最小之间的数的最左和最右然后因为扩张了区间，所以区间最大最尛值变化了继续返回上一步骤，继续寻找值在最大最小之间但是位置却在外面的数循环向两边扩张，直到r-l=max-min&nbs; 从这个思路可以发现，解釋唯一的