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}
$$