莫队

以为自己一辈子接触不到的算法,本来以为很高深,没想到是优雅的暴力,太绝妙了

对于多个区间查询,例如区间最大值等,我们考虑暴力,枚举区间 $[L,R]$,取最大值即可,时间复杂度 $O(m*(R-L))$,跑不起,所以我们借用数据结构,单调队列,树状数组等等,但是如果此时我们考虑优化暴露

首先我们这样优化: 设两个指针,然后如果左指针小于左端点,那么左指针向右走,依次遍历,这样可以减少遍历次数

其次: 考虑左指针,我们可以存取每个区间,然后按照区间的左端点排序,这样左指针最多走 $n$ 次,但是右端点无序,最坏仍然是 $O(n^2)$

那么我们能不能取个平衡呢? 也就是我们使左指针的复杂度升高,右指针的复杂度降低,此时我们考虑分块,一块一块的来求,我们把序列分为 $\sqrt{n}$ 块,然后对查询区间进行排序,如果左端点不在同一个块上,那么按照块大小排序,如果在一个块上,那么按照右端点进行排序
这样我们的左端点可以做到部分有序,右端点有序, 接下来讨论复杂度:

对于左指针:

设每个块 $i$ 中分布有 $x_i$ 个左端点，由于莫队的添加、删除操作复杂度为 $O(1)$，那么处理块 $i$ 的最坏时间复杂度是 $O(x_i\sqrt{n})$，指针跨越整块的时间复杂度为 $O(\sqrt{n})$，最坏需要跨越 $n$ 次；总复杂度 $O(\sum x_i \sqrt{n})=O(n\sqrt{n})$。

对于右指针:

由于在一个块内的右端点是有序的,那么我们遍历一个块时,右指针最坏移动 $n$ 个点,一共有$\sqrt{n}$个块,那么时间复杂度为: $O(n\sqrt{n})$

排序复杂度: $(O(n\log n)\)$

总复杂度: $O(n\sqrt{n})$

模板:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e6 + 10;

int a[N];
int pos[N];
int ans[N];
int res; // 维护当前[l,r]的值 

struct Query {
    int l, r, k;
}q[N];

void add(int pos){

}
void del(int pos){

}
int main () {
    int n, m;
    cin >> n >> m;
    
    int t = sqrt (n);
    for (int i = 1; i <= n; i ++) {    
        cin >> a[i];
        pos[i] = i / t + 1;
    }
    
    for (int i = 1; i <= m; i ++)
        cin >> q[i].l >> q[i].r;
    
    sort (q + 1, q + 1 + m, [](Query x, Query y) {
        return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
    });
    
    int l = 1, r = 0; // 始终维护[l,r]的答案，对于每一次询问都移动l,r指针，使其符合询问的区间 
    
    for (int i = 1; i <= m; i ++) {
        while (q[i].l < l) add (-- l); 
        while (q[i].r > r) add (++ r);
        while (q[i].l > l) del (l ++);
        while (q[i].r < r) del (r --);
        // 记录答案 ....
        ans[q[i].k] = res;
    }
    
    for (int i = 1; i <= m; i ++)
        cout << ans[i] << " "; 
    
    return 0;
} 

相关题:

0重复的数 - 蓝桥云课 (lanqiao.cn)

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N=2e5+10,mod=1e9+7;
int pos[N],a[N],cnt[N],ans[N],res[N];
struct node{
    int l,r,k,now;
    bool operator<(const node&w)const{
        return (pos[l]^pos[w.l])?pos[l]<pos[w.l]:((pos[l]&1)?r<w.r:r>w.r);
    }
}p[N];
void add(int x){
    ans[cnt[a[x]]]--,cnt[a[x]]++,ans[cnt[a[x]]]++;
}
void del(int x){
    ans[cnt[a[x]]]--,cnt[a[x]]--,ans[cnt[a[x]]]++;
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n; cin>>n;
    int len=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i],pos[i]=i/len;
    int m; cin>>m;
    for(int i=1;i<=m;i++){
        int a,b,c; cin>>a>>b>>c;
        p[i]={a,b,c,i};
    }
    sort(p+1,p+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        int num=p[i].k,id=p[i].now;
        while(l<p[i].l) del(l++);
        while(l>p[i].l) add(--l);
        while(r<p[i].r) add(++r);
        while(r>p[i].r) del(r--);
        res[id]=ans[num];
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<endl;
}

P2709 小B的询问 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10,mod=1e9+7;
int g[N],pos[N],a[N],cnt[N],ans;
struct node{
    int l,r,id;
    bool operator<(const node &w)const{
        return (pos[l]^pos[w.l])?pos[l]<pos[w.l]:((pos[l]&1)?r<w.r:r>w.r);
    }
}p[N];
void add(int x){
    cnt[a[x]]++,ans+=2*cnt[a[x]]-1;
}
void del(int x){
    ans-=2*cnt[a[x]]-1,cnt[a[x]]--;
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m,k; cin>>n>>m>>k;
    int len=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i],pos[i]=i/len;
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        p[i]={a,b,i};
    }
    sort(p+1,p+1+m);
    vector<int>res(m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l<p[i].l) del(l++);
        while(l>p[i].l) add(--l);
        while(r<p[i].r) add(++r);
        while(r>p[i].r) del(r--);
        res[p[i].id]=ans;
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<endl;
}