nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

例题1

http://codeforces.com/contest/617/problem/E

给长度为n的序列，给数字k，给q次询问,每次询问给出[L,R],求这个区间内有多少个连续区间的异或和等于k。

题解

预处理前缀异或和，化简区间为两个点异或值为k，再来莫队。

例题2

hdu5213，给你序列a，其长度为n，给你q个询问，每次询问给两个不相交的区间，求a[i]+a[j]=k的方案数，i属于第一个区间，j属于第二个区间。

(1≤N≤30000) (2≤K≤2*N) (1≤ai≤N)(1≤M≤30000) (1≤Li≤Ri<Ui≤Vi≤N)

题解

化简多区间为单区间询问，再来莫队

例题3

fzu2226， 给你长度为n的序列，定义第i个元素和第j个元素间的距离dis(i,j)=abs(i-j) 。给q个询问，每次询问一个区间[l,r]，要求你求出一对数字(i,j)(l<=i<=j<=r),使得a[i]=a[j]并且dis(i,j)最大，由于这样的数对可能有多个，因此答案只要输出dis。

N<=10^5 Q<=10^4 1<=a[i]<=10^3 1<=l<=r<=n

题解

莫队的时候，维护区间中每个值出现的最左下标和最右下标。

例题4

hdu4638， 给你一个长度为n的序列，m个询问，每次查询给一个区间，我们来划分这个区间，对于划分出的任意一个子区间，他的所有元素构成的集合所包含的数必须是一段连续的区间，然后定义区间的代价为区间长度的平方，定义划分的代价为划分结束后所有划分出的子区间的代价的和，询问此代价最高时的划分出的子区间的个数。

题解

可以证明，划分唯一，我们把划分操作看成切割原区间，定义划分的操作为切割点的位置的集合，若两个划分不一样，我们对这两个划分操作切割点集取交集，交集构成新的划分，此划分优于前两个划分。于是按照能合并就合并的贪心，我们可以找的最优划分。考虑莫队，当区间变化的时候：添加一个数，如果他左右的数字都存在，显然段数-1 若左右存在某一个，段数不变，若左右均不存在，则段数+1 ，删除同理。

例题5

hdu4676，给你一个排列，q个区间询问，求$\sum_{L\leq i<j\leq R}gcd(a_i,a_j) $

题解

反演出结果后，直接莫队，对新加进来的数，枚举他的因子，计算莫队区间的变化。
$$
\begin{aligned}
&n=id(n)=(1*\varphi)(n)=\sum_{d|n}\varphi(d)
\&\sum_{L\leq i<j\leq R}gcd(a_i,a_j)
\=&\sum_{L\leq i<j\leq R}\sum_{d|gcd(a_i,a_j)}\varphi(d)
\=&\sum_{L\leq i<j\leq R}\sum_{d|a_i}\sum_{d|a_j}\varphi(d)
\=&\sum_{d}\varphi(d)*C_{\sum_{i=L}^{R}[d|a_i]}^2
\end{aligned}
$$