基础知识：
莫队二次离线
题目让我们统计每个区间中有多少对 $a_i,a_j$ 满足 $a_i\oplus a_j$ 得出的值在二进制表示下有 $k$ 个 $1$。
异或 $\oplus$ 的运算逻辑：
例如：$5\oplus 3=6$
二进制表示：
这里如果 $k=2$ 那么如果 $5,2$ 在一个区间中这一对数就符合要求，可以统计。
$5\oplus 5=0$ 任何数异或自己为 $0$，那么根据这个特性就有：
也就是：
代码思路
- 读入，初始化基本信息。
由于每个元素的值都很小。所以可以预处理出，所有可以满足 $k$ 个 $1$ 的值。
后面通过这些值，在枚举值时，可以快速描述符合要求的“另一半”是谁。用的就是上面说异或的特性。
处理块长，将每个数分到对应块中。
- 将询问排序（第一次离线）。
排序的方式仍然时分奇偶块，奇升序，偶降序或者反之都可以（保证伸缩的程度尽量小）。
- 将区间的变化“量”存储（第二离线）。
每两个询问的“伸缩”的改变的范围存储，左端点，右端点的变化量分开存。
- 统计每个数能和前面后面分别匹配几个。
从前向后，从后向前分别扫一次。方法就是上面说的异或的特性。
每次扫的时候，将所有能匹配的值都累计，但是不是立刻用，而是遍历到后面直接用。
例如（瞎举的，仅是方便理解）：从前往后遍历，在遍历 $1$ 的时候，将后面的 $2,4,6$ 都标记了，那么 $2,4,6$ 的标记都增加 $1$。那么如果后面有 $4$ 这个值，就可以直接获取标记的值为 $1$，代表前面有一个可以匹配。
- 区间变化“量”的处理。
左右段点分开处理，现在假设枚举左端点，处理的右端点的变化“量”，我们实时更新前面有几个可以和当前节点匹配，将这些能匹配的对数都减去或加上。
因为左端点“回缩”或者“扩张”，要看存的时候是怎么变化的。
枚举右端点，处理左端点变化同理，但是处理的是当前节点能匹配后面的点有几对。
- 答案统计。
上个步骤处理完后，我们要求答案贡献的前缀和因为我们用莫队的时候是根据“伸缩”来变化的，而“伸缩”描述的是上一个状态变成新的状态做出的变化。简而言之，就是当前状态是在上一个状态的基础上实现的。
- 输出。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
int n,m,k;
int a_a[o_o];//初始序列
int x_c[o_o];//所有符合 k 个 1 要求的数（只有这些数符合要求，通过一个数，快速找另一个数）
int s_m;//一共有多少个符合 k 个 1 要求的数
int k_i[o_o];//每个数属于哪一块
int t_i[o_o];//实时更新符合要求的数
long long a_s[o_o];//统计结果
long long q_z[o_o],h_z[o_o];//符合情况的个数的前缀后缀
struct qq{
int l,r;
int i_d;//编号
}q_i[o_o];//第一次离线（新闻离线）
struct po{
int l,r;
int p;//判断加上或者减去
int i_d;//编号
};
vector<po>v_1[o_o],v_2[o_o];//第二次离线，变化离线，分为右端点变化和左端点变化
bool cmp(qq a,qq b){
//如果是一个块，如果是第一个数是奇数，右边从小到大，偶数从大到小
//如果不是一个块，块小的靠前
return(k_i[a.l]^k_i[b.l]?k_i[a.l]<k_i[b.l]:(k_i[a.l]&1?a.r<b.r:a.r>b.r));
}
int l_b(int x){
return x&(-x);
}
int g_h(int x){
int a_s=0;
while(x){
a_s++;
x-=l_b(x);
}
return a_s;
}
int main(){
n=r_r(),m=r_r(),k=r_r();
for(int i=1;i<=n;i++)a_a[i]=r_r();//读入原始序列
//16384 是 a_i 的数据范围
for(int i=0;i<=16384;i++)if(g_h(i)==k)x_c[++s_m]=i;//找出所有二进制下 1 的个数为 k 的数
int s_i=sqrt(n);//块长
for(int i=1;i<=n;i++)k_i[i]=(i-1)/s_i+1;//记录每个数属于那个块
for(int i=1;i<=m;i++){//所有询问记录（离线）
q_i[i].l=r_r();
q_i[i].r=r_r();
q_i[i].i_d=i;
}
sort(q_i+1,q_i+m+1,cmp);//将询问排序
int l=1,r=0;
for(int i=1;i<=m;i++){
//记录右边界
if(r<q_i[i].r)v_1[l].push_back((po){r+1,q_i[i].r,1,q_i[i].i_d});
if(r>q_i[i].r)v_1[l].push_back((po){q_i[i].r+1,r,-1,q_i[i].i_d});
r=q_i[i].r;//更新右边界
//记录左边界
if(l<q_i[i].l)v_2[r].push_back((po){l,q_i[i].l-1,-1,q_i[i].i_d});
if(l>q_i[i].l)v_2[r].push_back((po){q_i[i].l,l-1,1,q_i[i].i_d});
l=q_i[i].l;//更新左边界
}
for(int i=1;i<=n;i++){
q_z[i]=1ll*t_i[a_a[i]];//当前的数可以和几个前面的匹配成功
//所有可以和当前数异或后成为目标的数，累计答案
for(int j=1;j<=s_m;j++)t_i[a_a[i]^x_c[j]]++;
}
memset(t_i,0,sizeof(t_i));
for(int i=n;i>=1;i--){
h_z[i]=1ll*t_i[a_a[i]];//当前的数可以和几个后面的匹配成功
//所有可以和当前数异或后成为目标的数，累计答案
for(int j=1;j<=s_m;j++)t_i[a_a[i]^x_c[j]]++;
}
memset(t_i,0,sizeof(t_i));
for(int i=1;i<=n;i++){//左端点
for(int j=0;j<v_1[i].size();j++)//处理所有的右端点的情况
for(int k=v_1[i][j].l;k<=v_1[i][j].r;k++)//枚举范围
//统计答案，当前范围内能和前面匹配的对数
a_s[v_1[i][j].i_d]+=1ll*v_1[i][j].p*(q_z[k]-1ll*t_i[a_a[k]]);
//只能统计已经出现的贡献，所以要边处理，边更新贡献
for(int j=1;j<=s_m;j++)t_i[a_a[i]^x_c[j]]++;//累计答案
}
memset(t_i,0,sizeof(t_i));
for(int i=n;i>=1;i--){//右端点
for(int j=0;j<v_2[i].size();j++)//处理所有的左端点的情况
for(int k=v_2[i][j].l;k<=v_2[i][j].r;k++)//枚举范围
//统计答案，当前范围内能和后面匹配的对数
a_s[v_2[i][j].i_d]+=1ll*v_2[i][j].p*(h_z[k]-1ll*t_i[a_a[k]]);
//实时更新
for(int j=1;j<=s_m;j++)t_i[a_a[i]^x_c[j]]++;
}
//前缀和统计结果（莫队每回根据上一次的状态调整到目标状态，所以要获取上一次的“状态”）
for(int i=2;i<=m;i++)a_s[q_i[i].i_d]+=a_s[q_i[i-1].i_d];
for(int i=1;i<=m;i++)printf("%lld\n",a_s[i]);//输出所有询问的结果
return 0;
}
歴史の研究
题目要求每个区间范围的最大权值（$=$ 数的值 $\times $ 这个数的数量）。
回滚莫队思路
读入基本信息，分块。
离散化。
读取询问，离线操作。
询问排序。
住在不一个块中左端点排序，否则右端点排序，尽量减少“伸缩”次数。
- 处理每个询问。
如果在一个块中，单独处理直接解决。
如果右端点在块外，往外延伸，记录此时的最大值。
如果左端点在块外，往外延伸，但是最后找到最大值后，记结果后，要将左边再缩回来。此时最大值也更新为上面记录的最大值。在排序时，我们的右端点是有序的。
- 将询问的顺序排回来，按顺序输出。
回滚莫队代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const long long o_o=2e5+10;
struct po{
long long x,y;//左右端点
long long i_d;//记录第几个询问
long long a_s;//记录结果
}q_i[o_o];//询问信息
struct pp{
long long x_x;//原始序列
long long i;//编号
}a_a[o_o];//节点信息
long long k_i;//块长
long long b_b[o_o];//当前节点在那个块中
long long x_x[o_o];//离散化
long long b_p[o_o];//统计块内每个数出现的数量
long long c_p[o_o];//存原值
long long m_m[o_o];//临时数组，处理在一个块内时每个点出现的次数
long long m_a;//最大值
long long k_k;//处理到第几个询问了
long long n,m;
bool c_1(pp a,pp b){//将值从小到大排序
return a.x_x<b.x_x||(a.x_x==b.x_x&&a.i<b.i);
}
bool c_2(po a,po b){
if(b_b[a.x]!=b_b[b.x])return a.x<b.x;//不是一个块，按左端点排序
return a.y<b.y;//是同一个块按右端点排序
}
bool c_3(po a,po b){//按照询问的先后顺序排序
return a.i_d<b.i_d;
}
long long f_i(long long l,long long r){
long long m_k=0;//初始化最大值
for(long long i=l;i<=r;i++)m_m[x_x[i]]=0;//初始化，清空
for(long long i=l;i<=r;i++){
m_m[x_x[i]]++;//更新值出现的次数
m_k=max(m_k,m_m[x_x[i]]*c_p[i]);//更新最大值
}
return m_k;//返回最大值
}
long long g_i(long long k_k,long long x){
m_a=0;
long long l_t=0;
long long i=k_k;//记录处理到第几个询问了
for(long long j=1;j<=n;j++)b_p[j]=0;//初始化
long long l_r=min(k_i*x,n);
long long l=l_r+1,r=l_r;//当前块左端
while(b_b[q_i[i].x]==x){//当前询问的左端点还在当前块
if(b_b[q_i[i].x]==b_b[q_i[i].y]){//左右端点在同一个块中
q_i[i].a_s=f_i(q_i[i].x,q_i[i].y);//记录结果
i++;//下一个
continue;
}
while(r<q_i[i].y){//右端点未达到询问
b_p[x_x[++r]]++;//右端点外延
m_a=max(m_a,b_p[x_x[r]]*c_p[r]);//更新最大值
}
l_t=m_a;//记录最大值
while(l>q_i[i].x){//左端点未达询问
b_p[x_x[--l]]++;//左端点外延
m_a=max(m_a,b_p[x_x[l]]*c_p[l]);//更新最大值
}
q_i[i].a_s=m_a;//更新最大值
while(l<l_r+1)b_p[x_x[l++]]--;//左端点恢复到块左端
m_a=l_t;//更新最大值
i++;//下一个询问
}
return i;//返回进行到哪个询问了
}
int main(){
n=r_r(),m=r_r();
k_i=sqrt(n);//分块
for(long long i=1;i<=n;i++){
a_a[i].x_x=r_r();//读入原始序列
c_p[i]=a_a[i].x_x;//复制
a_a[i].i=i;//记录位置
b_b[i]=(i-1)/k_i+1;//记录属于哪一块
}
long long n_m=b_b[n];//记录一共有多少块
sort(a_a+1,a_a+n+1,c_1);//值从小到大排序
for(long long i=1,j=0;i<=n;i++){//离散化
if(i==1||a_a[i].x_x!=a_a[i-1].x_x)j++;
x_x[a_a[i].i]=j;
}
for(long long i=1;i<=m;i++){//读入询问（离线）
q_i[i].x=r_r();
q_i[i].y=r_r();
q_i[i].i_d=i;
}
k_k=1;
sort(q_i+1,q_i+m+1,c_2);//询问排序
for(long long i=1;i<=n_m;i++)k_k=g_i(k_k,i);//处理每个块
sort(q_i+1,q_i+m+1,c_3);//顺序排序
for(long long i=1;i<=m;i++)//输出
printf("%lld\n",q_i[i].a_s);
return 0;
}分块思路
这回分块不再是将整个序列分成小块，而是将整个序列看成第一块，然后不断将左端右移但有段不动，分成不同大小的块。
例如：现在又序列长度 $64$ 的一个区间，那么第一个块：$[1,64]$，将左端右移，有段动根据块长分成第二块：$[9,64]$，第三块：$[17,64]…$
我们在每块处理最大值和每个数出现的次数（由于数的范围过大，但数量小，所以要离散化）。
每个块在处理最大值的时候，我们还要将右端点记录。就是左端点分块，但是右端点暴力枚举。
然后处理询问，我们已经与处理好块了，所以可以在线处理。首先找到左端点在的块中，然后找到下一个块到右端点之间的最大值（处理块的时候有端点是暴力的）。
最后处理左端点所在的块的情况。
将块中范围内的数全部记录到一个数组中。并统计每个数出现的次数。统计每个数在整个区间出现的次数：
左边部分：暴力统计（刚刚已经完成了）。
中间部分：左端点所在的块的下一个块和右端点所在的块之间数量差（就是到右段点块之前这个数出现的次数）。
右边部分：暴力统计右端点所在的块范围内每个数的贡献。
同时通过每个数的贡献不断更新最大权值，输出即可。
分块代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
int n=r_r(),q=r_r();
int k_i;//块长
int a_a[o_o];//原序列
int b_b[o_o];//当前值属于那个块
long long c_p[o_o];//辅助数组（离散化）
long long f_i[500][o_o];//每个块到每个数的最大值
long long c_t[500][o_o];//每块中，每个数出现的数量
long long s_t[o_o];//对于块内讨论的队列
long long n_m[o_o];//数出现的次数
int main(){
k_i=sqrt(n);//块长
for(int i=1;i<=n;i++){
a_a[i]=r_r();//原始序列
b_b[i]=(i-1)/k_i+1;//属于哪个块
c_p[i]=a_a[i];//复制
}
sort(c_p+1,c_p+1+n);//排序
int k_b=unique(c_p+1,c_p+1+n)-c_p-1;//去重
for(int i=1;i<=n;i++)a_a[i]=lower_bound(c_p+1,c_p+1+k_b,a_a[i])-c_p;//离散化
for(int i=1;i<=b_b[n];i++){//处理每个块
long long n_w=0;
for(int j=lower_bound(b_b+1,b_b+1+n,i)-b_b;j<=n;j++){//第 i 块开头和之后的部分
c_t[i][a_a[j]]++;//累计块中当前值相同的数的个数
n_w=max(n_w,c_t[i][a_a[j]]*c_p[a_a[j]]);//统计最大值
f_i[i][j]=n_w;//记录最大值
}
}
while(q--){
int x=r_r(),y=r_r();//询问区间
long long a_s=f_i[b_b[x]+1][y];//从 x 的块开始到 y 的最大值
int t_p=0;//队列“清空”
int t_m=lower_bound(b_b+1,b_b+1+n,b_b[y])-b_b;//y 所在块的开头
for(int i=t_m;i<=y;i++){
n_m[a_a[i]]++;//统计出现次数
s_t[++t_p]=a_a[i];//入队
}
t_m=lower_bound(b_b+1,b_b+1+n,b_b[x]+1)-b_b;//x 所在块的结尾 +1
for(int i=x;i<t_m;i++){
n_m[a_a[i]]++;//统计出现次数
s_t[++t_p]=a_a[i];//入队
//统计最大值（套公式）
a_s=max(a_s,(c_t[b_b[x]+1][a_a[i]]-c_t[b_b[y]][a_a[i]]+n_m[a_a[i]])*c_p[a_a[i]]);
}
for(int i=1;i<=t_p;i++)n_m[s_t[i]]=0;//清空
printf("%lld\n",a_s);//输出
}
return 0;
}
回滚莫队&不删除莫队
题目让维护的是在区间内两值的最远距离。在处理每个值时，如果第一次出现，记录位置没否则的话就尝试更新最大值。
初始化，读入基本信息，分块。
离散化。
询问离线，排序。
在一块内，所有询问左端点在块内的都进行处理，如果走右端点都在块内，单独处理。
记录最大值，顺序输出。
和上面的题的思路相似。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e6+10;
int m_b;//数列去重的数量
int n,m;
int a_a[o_o];//原数列
int a_s[o_o];//答案
int m_a[o_o];//当前值的位置记录
int b_b[o_o];//属于那个块
int b_n;//块的数量
int c_p[o_o];//复制
int s_t[o_o];//存当前值第一次在区间中出现的位置
int x_p;//已经记录几个不同的值
int n_w[o_o];//每个不同的值是谁
struct po{
int l,r;//左右端点
int i;//编号
bool operator <(const po &n)const{
//再一个块中，按右端点排序否则，按块排序
return (b_b[l]^b_b[n.l])?b_b[l]<b_b[n.l]:r<n.r;
}
}q_i[o_o];
int f_i(int l,int r){
int l_t[o_o],r_s=0;
for(int i=l;i<=r;i++)l_t[a_a[i]]=0;//清空
for(int i=l;i<=r;i++)
if(!l_t[a_a[i]])l_t[a_a[i]]=i;//记录
else r_s=max(r_s,i-l_t[a_a[i]]);//更新最小值
return r_s;
}
int main(){
n=r_r();
int k_i=sqrt(n);//块长
for(int i=1;i<=n;i++){
a_a[i]=r_r();
c_p[i]=a_a[i];//复制
b_b[i]=(i-1)/k_i+1;//判断属于哪个块
}
b_n=b_b[n];//存储块数
sort(c_p+1,c_p+1+n);//排序
m_b=unique(c_p+1,c_p+1+n)-c_p-1;//去重
for(int i=1;i<=n;i++)a_a[i]=lower_bound(c_p+1,c_p+1+m_b,a_a[i])-c_p;//离散化
m=r_r();
for(int i=1;i<=m;i++){//读入询问离线
q_i[i].l=r_r();
q_i[i].r=r_r();
q_i[i].i=i;
}
sort(q_i+1,q_i+1+m);//询问排序
for(int i=1,j=1;j<=b_n;j++){//处理每一块
int k_k=min(n,j*k_i);
int l=k_k+1,r=l-1;//当前块的左右范围
int r_s=0;
x_p=0;
while(b_b[q_i[i].l]==j){//左端点在当前块内
if(b_b[q_i[i].r]==j){//左右端点在同一块中
a_s[q_i[i].i]=f_i(q_i[i].l,q_i[i].r);//统计结果
i++;//下一询问
continue;
}
while(r<q_i[i].r){//右阔
r++;
m_a[a_a[r]]=r;//更新
if(!s_t[a_a[r]]){//记录
s_t[a_a[r]]=r;
n_w[++x_p]=a_a[r];
}
r_s=max(r_s,r-s_t[a_a[r]]);//更新最大值
}
int t_p=r_s;//记录最大值
while(l>q_i[i].l){//左阔
l--;
if(m_a[a_a[l]])r_s=max(r_s,m_a[a_a[l]]-l);//更新最大值
else m_a[a_a[l]]=l;//记录
}
a_s[q_i[i].i]=r_s;//记录结果
while(l<=k_k){//将左端点缩回来
if(m_a[a_a[l]]==l)m_a[a_a[l]]=0;//清空
l++;
}
r_s=t_p;//更新最大值
i++;//下一个询问
}
for(int i=1;i<=x_p;i++)m_a[n_w[i]]=s_t[n_w[i]]=0;//清空
}
for(int i=1;i<=m;i++)printf("%lld\n",a_s[i]);//输出结果
return 0;
}
