题解 P2709 【小B的询问】

一只小兵 · 2019-08-07 21:48:40 · 题解

题面分析

对区间中数的出现次数进行离线查询,是一道莫队的模板题

普通莫队

莫队

莫队算法是由莫涛发明的算法，所以称为莫队算法。主要用来处理离线的区间问题，如区间和。

莫队算法能解决的情况

离线询问.例如P4168就不能用带修莫队
对于每次加入区间的操作的复杂度都是O(1)的.如查找区间众数就是删除一个数的复杂度不是O(1)的.(使用回滚莫队其实也是将区间移动降为复杂为O(1)，这里不做讨论)

算法过程

对于多段区间的询问,先将询问离线存储下来,然后再从左到右扫一遍,在过程中维护一段区间,就可以得到每个寻问的答案.
但暴力扫肯定不行，所以在扫的过程中,需要对 l 进行排序,以求能够在移动次数最少的情况下,得到所有希望求出的区间.
首先对每个区间进行分块操作,再将左端点在一起的区间询问放在一起进行处理,对于每个块处理一遍,那么就可以得到所有询问的答案.
还是用图来展示一下过程

预处理

然后对问题进行排序

~~因为太懒了,区间长度都一样~~

开始莫队

初始化左右指针

移动右端点到第一个位置,这时满足了第一个区间

 移动左端点                                         到达第二个位置

后面类推,就不一一说明了

最终状态

复杂度证明

对于区间进行分块那么可以得到\sqrt{n}个块,那么对于就存在于\sqrt{n}个区间,而每次对于每个区间块中的l ,r的最坏情况是对于每个块都遍历到序列的最右端,共n个点.每次移动指针复杂度为O(1),所以整个算法的复杂度为O(n\sqrt{n})

代码思路

对于问题的离线化分块处理

struct question{
int l,r,num;//表示从l到r 和 第num个问题
bool operator<(const question p1) const {//对于一个问题进行排序处理,将l的块在前的放在一起,再按r为第二关键字排序
if(i[this->l] != i[p1.l]) return this->l < p1.l;
else if(i[this->l]&1){//这里有一个小技巧,将r按照奇数顺序,偶数逆序排序
      return this->r < p1.r;
  }
    else return this->r > p1.r;
}
}q[maxn];

关于小技巧的说明:对于两个区间交替的过程中,r如果先回来,那么部分点就会被扫两次,那么对于r一正一逆的排序,就可以避免重复的情况

//可能有人不太喜欢结构体函数,这里在写一份cmp的排序. 
struct question{
  int l,r,num;
}; 
bool cmp(question p1, question p2){
  if(i[p1.l] != i[p2.l]) return i[p1.l] < i[p2.l];
  if(p1.l % 2 == 0) return p1.r > p2.r;
  return p1.r < p2.r; 
}

目标区间指针的移动(莫队核心)

for(int t = 2; t <= m ; t++){
    for(; l_now < q[t].l ; l_now++) {//将l指针(绿色)向右移动
        ans -= (cnt[a[l_now]]*cnt[a[l_now]]);//将一个点移出区间
        cnt[a[l_now]]--;
        ans += (cnt[a[l_now]]*cnt[a[l_now]]);
    }
    for(++r_now;r_now <= q[t].r ; r_now++){//将r指针(红色)向右移动
        ans -= (cnt[a[r_now]]*cnt[a[r_now]]);//将一个点加入区间
        cnt[a[r_now]]++;
        ans += (cnt[a[r_now]]*cnt[a[r_now]]);
    }
    for(--l_now ; l_now >= q[t].l ; l_now--){//将l指针向左移动
        ans -= (cnt[a[l_now]]*cnt[a[l_now]]);//将一个点移出区间
        cnt[a[l_now]]++;
        ans += (cnt[a[l_now]]*cnt[a[l_now]]);
    }
    for(--r_now; r_now > q[t].r ; r_now--){//将r指针向左移动
        ans -= (cnt[a[r_now]]*cnt[a[r_now]]);//将一个点移出区间
        cnt[a[r_now]]--;
        ans += (cnt[a[r_now]]*cnt[a[r_now]]);
    }
    pri[q[t].num] = ans;l_now=q[t].l;r_now=q[t].r;//将移过的指针复原
}

注意：

要将最终答案按顺序进行存储

最后附上AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 50017;
int a[maxn],i[maxn],l_now,r_now,cnt[maxn];//a储存原序列,i储存位置所在块,l_now,r_now分别是当前目标区间,cnt表示出现次数 
long long ans,pri[maxn];
struct question{
    int l,r,num;//表示从l到r 和 第num个问题
    bool operator<(const question p1) const {//对于一个问题进行排序处理,将l的块在前的放在一起,再按r为第二关键字排序
    if(i[this->l] != i[p1.l]) return this->l < p1.l;
    else if(i[this->l]&1){//这里有一个小技巧,将r按照奇数顺序,偶数逆序排序
            return this->r < p1.r;
        }
        else return this->r > p1.r;
    }
}q[maxn];
int main(){
    int n,m,k,q_m;
    scanf("%d%d%d",&n,&m,&k);
    q_m = sqrt(m);
    for(int t = 1 ; t <= n ; t++){
        scanf("%d",&a[t]);
        i[t] = (t-1)/q_m+1;//找到t位置所在的块
    }
    for(int t = 1 ; t <= m ; t++){
        scanf("%d%d",&q[t].l,&q[t].r);
        q[t].num=t;
    }
    sort(q+1,q+1+m);//对进行问题排序 
    for(int t = q[1].l ; t <= q[1].r ; t++){//先暴力求出第一个问题的答案 
        ans -= (cnt[a[t]]*cnt[a[t]]);
        cnt[a[t]]++;
        ans += (cnt[a[t]]*cnt[a[t]]);
    }
    l_now = q[1].l;r_now = q[1].r;pri[q[1].num] = ans;//当前的节点 
    for(int t = 2; t <= m ; t++){
        for(; l_now < q[t].l ; l_now++) {//将l指针(绿色)向右移动
            ans -= (cnt[a[l_now]]*cnt[a[l_now]]);//将一个点移出区间
            cnt[a[l_now]]--;
            ans += (cnt[a[l_now]]*cnt[a[l_now]]);
        }
        for(++r_now;r_now <= q[t].r ; r_now++){//将r指针(红色)向右移动
            ans -= (cnt[a[r_now]]*cnt[a[r_now]]);//将一个点加入区间
            cnt[a[r_now]]++;
            ans += (cnt[a[r_now]]*cnt[a[r_now]]);
        }
        for(--l_now ; l_now >= q[t].l ; l_now--){//将l指针向左移动
            ans -= (cnt[a[l_now]]*cnt[a[l_now]]);//将一个点移出区间
            cnt[a[l_now]]++;
            ans += (cnt[a[l_now]]*cnt[a[l_now]]);
        }
        for(--r_now; r_now > q[t].r ; r_now--){//将r指针向左移动
            ans -= (cnt[a[r_now]]*cnt[a[r_now]]);//将一个点移出区间
            cnt[a[r_now]]--;
            ans += (cnt[a[r_now]]*cnt[a[r_now]]);
        }
        pri[q[t].num] = ans;l_now=q[t].l;r_now=q[t].r;//将移过的指针复原
    }   
    for(int t = 1 ; t <= m ; t++)
        printf("%lld\n",pri[t]);
    return 0;
}