G. Magic Number Group 题解(莫队 区间众数问题)

[题目链接]https://codeforces.com/gym/103366/problem/G)

题目思路

其实仔细分析就是一个区间众数问题，温习一下

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,block;
int a[maxn];
int num[maxn],ans[maxn];
int ma;
int dp[maxn];
struct node{
    int l,r,id;
}q[maxn];
bool cmp(node x, node y)
{
    if (x.l / block != y.l / block)
        return x.l < y.l;
    else if ((x.l / block) & 1)
        return x.r < y.r;
    else
        return x.r > y.r;
}
int prime[maxn],cnt;
int isprime[maxn];
void getprime(int n){
    for(ll i=2;i<=n;i++){//开ll因为后面要计算i*prime[j]
        if(!isprime[i]){
            isprime[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            isprime[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}
void add(int x){
    while(isprime[x]){
        int tmp=isprime[x];
        while(isprime[x]==tmp){
            x/=isprime[x];
        }
        num[tmp]++;
        dp[num[tmp]]++;
        dp[num[tmp]-1]--;
        ma=max(ma,num[tmp]);
    }
}
void del(int x){
    while(isprime[x]){
        int tmp=isprime[x];
        while(isprime[x]==tmp){
            x/=isprime[x];
        }
        if(ma==num[tmp]&&dp[num[tmp]]==1){
            ma=num[tmp]-1;
        }
        num[tmp]--;
        dp[num[tmp]]++;
        dp[num[tmp]+1]--;
    }
}
int main(){
    getprime(1000000);
    int _;scanf("%d",&_);
    while(_--){
        ma=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        block=sqrt(n);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+1+m,cmp);
        int l=1,r=1;
        add(a[1]);
        for(int i=1;i<=m;i++){
            while(l<q[i].l) del(a[l++]);
            while(l>q[i].l) add(a[--l]);
            while(r<q[i].r) add(a[++r]);
            while(r>q[i].r) del(a[r--]);
            ans[q[i].id]=ma;
        }
        for(int i=l;i<=r;i++){
            del(a[i]);
        }
        for(int i=1;i<=m;i++){
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}