题目链接

#6164. 「美团 CodeM 初赛 Round A」数列互质

询问 l,r，k <script type="math/tex" id="MathJax-Element-16">l,r，k</script> 中次数的次数与互质的个数.

分析

维护区间中数的个数，这一眼看过去不就是 莫队吗，可以看到对于次数的次数最多只有 n−−√ <script type="math/tex" id="MathJax-Element-128">\sqrt n</script> 种因此我们可以暴力处理每次查询，用一个链表维护次数的次数就好复杂度 O(nn−−√+Qn−−√logn) <script type="math/tex" id="MathJax-Element-129">O(n\sqrt n+ Q\sqrt nlog n)</script>

开始用hash map维护，T了…,网上看了大神的写法才发现直接用链表维护次数，算的时候可以 O(1) <script type="math/tex" id="MathJax-Element-130">O(1)</script> 处理….

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 50000+10;
int n,m;
struct Query{
    int l,r,k,id;
};
Query q[maxn];
int ans[maxn],a[maxn];
const int S = 225;
bool cmp(const Query& a, const Query& b){
    return (a.l/S)==(b.l/S)?a.r < b.r : a.l < b.l;
}

int cnt[maxn<<2];
int um[maxn<<2];
//链表
int nt[maxn<<2],last[maxn<<2],head=0,tail = maxn-1;
inline void insert(int x){if(x<=head)return;nt[x]=nt[head];nt[head]=x;last[x]=head;last[nt[x]]=x;}
inline void remove(int x){if(x<=head)return;nt[last[x]] = nt[x];last[nt[x]] = last[x];}
inline void move(int val,int sign){
    if(sign){//加
        if(--um[cnt[val]] ==0)remove(cnt[val]);
        if(++um[++cnt[val]]==1)insert(cnt[val]);
    }else{
        if(--um[cnt[val]] ==0)remove(cnt[val]);
        if(++um[--cnt[val]]==1)insert(cnt[val]);
    }
}
void solve(){
    int curL=q[0].l,curR =q[0].l-1;
    for(int i=0 ; i<m ; ++i){
        int L = q[i].l,R= q[i].r,k=q[i].k;
        while (curL<L){move(a[curL++],0);}
        while (curL>L){move(a[--curL],1);}
        while (curR<R){move(a[++curR],1);}
        while (curR>R){move(a[curR--],0);}
        int ret =0;
        for(int x = nt[head] ; x !=tail ; x = nt[x])
            if(__gcd(x,k) == 1)ret += um[x];
        ans[q[i].id] = ret;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    nt[0] = tail;last[tail] = 0;
    for(int i=1 ; i<=n ; ++i)cin>>a[i];
    for(int i=0 ; i<m ; ++i){
        q[i].id=i;cin>>q[i].l>>q[i].r>>q[i].k;
    }
    sort(q,q+m,cmp);
    solve();
    for(int i=0 ; i<m ; ++i)cout << ans[i] << '\n';
//     cout << clock() <<" ms" << endl;
    return 0;
}