Si_Yue小屋
0%

莫队算法

发表于 分类于

莫队算法指的是将询问离线下来，对于原序列分块，按照不同块之间按照左端点排序，同一块之间按照右端点排序（奇偶优化的情况下需满足左端点在奇数块中的询问按右端点升序，左端点在偶数块中的询问按照右端点降序）。然后遍历所有的询问，去做好将维护区间左右伸长和缩短的贡献的方法，然后用定义好的方法记录将上次的 \(l\)，\(r\) 转移到现在的 \(q[i].l\) 和 \(q[i].r\) 的贡献变化。可以证明，时间复杂度为 \(O(n\sqrt{m})\) 的，注意分块的长度 \(len = n/\sqrt{m}\) ，否则不能保证时间复杂度。通常下 \(m\) 是 \(n\) 的量级，取长度为 \(\sqrt{n}\)，此时时间复杂度为 \(O(n ^ {\frac{3}{2}})\) 。

例题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>

using namespace std;

#define int long long

int read(){
    int res=0,sign=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')sign=-sign;
    for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch^'0');
    return res*sign;
}

const int N=5e4+10;

int n,m,len;
int c[N],id[N];

struct query_t{
    int l,r,idx;
    bool operator<(const query_t& o)const{
        if(id[l]!=id[o.l])return l<o.l;
        return (id[l]&1)?r<o.r:r>o.r;
    }
};

int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}

struct ans_t{
    int p,q;
    
    void setans(int _p,int _q){
        int _gcd=gcd(_p,_q);
        p=_p/_gcd,q=_q/_gcd;
    }
};

query_t q[N];
ans_t ans[N];

int sum,cnt[N];

void add(int i){
    sum+=cnt[i];
    ++cnt[i];
}

void del(int i){
    --cnt[i];
    sum-=cnt[i];
}

signed main(){
    // freopen("C:\\Users\\ASUS\\Downloads\\P1494_7.in","r",stdin);
    n=read(),m=read();
    len=sqrt(n);
    for(int i=1;i<=n;++i){
        c[i]=read();
        id[i]=(i-1)/len+1;
    }
    for(int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].idx=i;
    }
    sort(q+1,q+1+m);
    
    for(int i=1,l=1,r=0;i<=m;++i){
        int idx=q[i].idx;
        if(q[i].l==q[i].r){
            ans[idx].setans(0,1);
            continue;
        }
        while(l>q[i].l)add(c[--l]);
        while(r<q[i].r)add(c[++r]);
        while(l<q[i].l)del(c[l++]);
        while(r>q[i].r)del(c[r--]);
        ans[idx].setans(sum,(r-l+1)*(r-l)/2);
    }
    for(int i=1;i<=m;++i){
        printf("%lld/%lld\n",ans[i].p,ans[i].q);
    }
}

需要注意的是，奇偶分块优化的时候不能有小于等于，大于等于，不然会出问题。然后四个while的顺序按照先考虑区间的伸长，然后考虑缩短，伸长和缩短中都先考虑左端点，然后右端点。