基础莫队例题

基础莫队例题 引入

看了很多篇解释，我个人理解是莫队是优化后的双指针算法；

比如说我们现在要维护区间内数字出现的次数；

从 [ A , B ] [A,B] [A,B]区间转移到 [ C , D ] [C,D] [C,D]区间；

对于 B B B到 D D D的过程，就是不断的新增数字，如果这个数字的种类是第一次出现，那么就++ans；

对于 A A A到 C C C的过程，就是不断的减少数字，如果这个数字出现的次数已经归零了，那么就--ans；

---

以上的转移可以做到

但是现在我们的询问是乱序的，那么我们可以将所有的询问存下来，并且排个序；

---

为了使得时间复杂度降低到 O ( n n ) O(nsqrt{n}) O(nn ​)，以左端点的块号作为第一关键字升序排序，以右端点的值递增或递减排序(见后面玄学优化解释)；

如此我们就可以使得大体有序，从而快速推演；

---

初始化

扩展

玄学优化 一、

二、

奇偶排序；

具体 *** 作如下；

对于左端点在同一奇数块的区间，右端点按升序排列，反之降序；

而处于不同块的排序和之前一样，按左端点块号升序排序；

代码如下；

bool cmp(Query &p,Query &q){
    //先按左端点所在块排
    if(get(p.l) != get(q.l)) return get(p.l) < get(q.l);
    //如果编号相同说明在同一块
    //奇偶排序
    //奇数升序 偶数降序
    if(get(p.l) & 1) return p.r < q.r;
    return p.r > q.r;
}

它的主要原理便是右指针跳完奇数块往回跳时
在同一个方向能顺路把偶数块跳完;
然后跳完这个偶数块又能顺带把下一个奇数块跳完。
理论上主算法运行时间减半，实际情况有所偏差。

例题 HH的项链 题面

传送门

思路

模板题，该讲的上面都讲啦；

这里讲一下块的大小怎么取；

---

假设块长为 S S S，那么就有 n / S n/S n/S个块；

对于右指针来说，每一个快最坏情况下可能移动 n n n次；

一共 n / S n/S n/S个块；

那么复杂度为 O ( n 2 / S ) O(n^2/S) O(n2/S)

对于左端点来说

块内：每次移动最多不会超过 S S S 次，最坏情况总共 m S mS mS 次；

块间：即这一块最后询问到下一块第一个询问，下一个询问左端点一定是大于这个询问左端点的。所以总复杂度不超过 n n n

只需要使得两边尽可能平均，即满足 n 2 / S = m S n^2/S = mS n2/S=mS

解得 S = n / m S=n/ sqrt{m} S=n/m ​

---

简单一点，直接取最简单的 n sqrt{n} n ​也是可以过的；

---

至于处理每个询问的那几个while，自己手推一下，很容易理解；

仔细想一想当前的数是取还是删，或者得去 *** 作下一个数

不过要注意x++,++x,x--,--x的区别！

Code

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 5e4 + 10,M = 1000000 + 10;

int a[N],n,m,ans[2*M];

int cnt[M],len,res;

struct Query{
    int l,r,id;
}query[M*2];

int get(int x){
    return x / len;
}
bool cmp(Query &p,Query &q){
    //先按左端点所在块排
    if(get(p.l) != get(q.l)) return get(p.l) < get(q.l);
    //如果编号相同说明在同一块
    //奇偶排序
    //奇数升序 偶数降序
    if(get(p.l) & 1) return p.r < q.r;
    return p.r > q.r;
}
void add(int x){
    if(cnt[x] == 0) ++res;
    ++cnt[x];
}
void del(int x){
    --cnt[x];
    if(cnt[x] == 0) --res;
}
void solve(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    cin >> m;
    len = n / sqrt(m);
    //防止毒瘤数据使得len为0
    if(len == 0) len = sqrt(n);
    for(int i=1;i<=m;++i){
        cin >> query[i].l >> query[i].r;
        query[i].id = i;   
    }
    sort(query+1,query+1+m,cmp);
    int L = 1,R = 0;
    for(int i=1;i<=m;++i){
        while(L < query[i].l) del(a[L++]);
        while(L > query[i].l) add(a[--L]);
        while(R < query[i].r) add(a[++R]);
        while(R > query[i].r) del(a[R--]);
        ans[query[i].id] = res;
    }
    for(int i=1;i<=m;++i) cout << ans[i] << 'n';
}

int main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

Magic Number Group 题面

传送门

题意

简单来说就是给定一个区间，问我们任意取一个数，请问最多能整除这个区间里的多少数；

思路

考虑分解质因数，转化为莫队维护区间众数出现次数的问题；

s u m ( i ) sum(i) sum(i)表示出现i次的数有几个

c n t ( i ) cnt(i) cnt(i)表示i这个数出现的次数

Code

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 5e4 + 10,M = 1e6;

vector fact[M + 5];//维护每个数的所有质因子

bool vis[M + 5];

void init(){
    //考虑每个数能成为谁的因子
    for(int i=2;i<=M;++i){
        if(vis[i]) continue;
        for(int j=1;j*i<=M;++j){
            vis[j*i] = 1;
            fact[j*i].push_back(i);
        }
    }
}

int len;

int get(int x){
    return x / len;
}
struct Ask{
    int l,r,id;
    bool operator<(const Ask &other)const{
        if(get(l) != get(other.l)){
            return get(l) < get(other.l);
        }
        if(get(l) & 1){
            return r < other.r;
        }
        return r > other.r;
    }
}ask[N];

int n,q,a[N];

//sum[i]表示出现i次的数有几个
//cnt[i]表示i这个数出现的次数
int sum[M + 5],cnt[M + 5],mx;

void add(int x){
    for(auto &p : fact[x]){
        --sum[cnt[p]];
        ++cnt[p];
        ++sum[cnt[p]];
        mx = max(mx,cnt[p]);
    }
}
void del(int x){
    for(auto &p : fact[x]){
        --sum[cnt[p]];
        if(cnt[p] == mx && sum[cnt[p]] == 0){
            --mx;
        }
        --cnt[p];
        ++sum[cnt[p]];
    }
}
int ans[N];
void solve(){
    mx = 0;
    cin >> n >> q;
    for(int i=1;i<=n;++i) cin >> a[i];
    len = sqrt(n);
    int l,r;
    for(int i=1;i<=q;++i){
        cin >> l >> r;
        ask[i] = {l,r,i};
    }
    sort(ask+1,ask+1+q);
    l = 1,r = 0;
    for(int i=1;i<=q;++i){
        while(l < ask[i].l) del(a[l++]);
        while(l > ask[i].l) add(a[--l]);
        while(r < ask[i].r) add(a[++r]);
        while(r > ask[i].r) del(a[r--]);
        ans[ask[i].id] = mx;
    }
    for(int i=1;i<=q;++i){
        cout << ans[i] << 'n';
    }
    //清空操作
    while(l <= r) del(a[l++]);
}

int main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

参考资料

dalao1
dalao2
墨巨