题解 P12598 参数要吉祥

meyi · 2025-05-24 21:14:22 · 题解

莫队是容易看出来的，但值域分块太难了，有没有用更简单的数据结构的做法？

有的兄弟，令 cnt_i 表示 i 这个数在 a 中的出现次数，容易发现 cnt 中最多只有 O(\sqrt n) 种不同的值。于是用链表维护这些值，O(1) 加入删除，O(\sqrt n) 遍历整个链表查询即可。

总时间复杂度 O(n\sqrt n)，常数很小，最慢点 0.4s。

代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
    int t_case=1;
    //scanf("%d",&t_case);
    while(t_case--){
        int n,q;
        scanf("%d%d",&n,&q);
        V<int>a(n);
        for(int &i:a)scanf("%d",&i);
        V<int>l(q),r(q);
        For(i,q)scanf("%d%d",&l[i],&r[i]),--l[i],--r[i];
        int m=*max_element(ALL(a))+1;
        V<int>c(m),cnt(n+1),nxt(n+1),pre(n+1);
        auto link=[&](int x){
            int y=nxt[0];
            pre[x]=0,nxt[x]=y;
            pre[y]=x,nxt[0]=x;
        };
        auto cut=[&](int x){
            int y=pre[x],z=nxt[x];
            pre[z]=y,nxt[y]=z;
        };
        auto add=[&](int k){
            if(c[k]){
                if(!--cnt[c[k]])cut(c[k]);
            }
            if(!cnt[++c[k]]++)link(c[k]);
        };
        auto del=[&](int k){
            if(!--cnt[c[k]])cut(c[k]);
            if(--c[k]){
                if(!cnt[c[k]]++)link(c[k]);
            }
        };
        const int B=ceil(n/sqrt(q));
        V<int>bel(n);
        FOR(i,B,n)bel[i]=bel[i-B]+1;
        V<int>id(q);
        iota(ALL(id),0);
        sort(ALL(id),[&](int x,int y){return bel[l[x]]!=bel[l[y]]?l[x]<l[y]:(bel[l[x]]&1)?r[x]>r[y]:r[x]<r[y];});
        V<int>ans(q);
        int pl=0,pr=-1;
        for(int i:id){
            while(pl>l[i])add(a[--pl]);
            while(pr<r[i])add(a[++pr]);
            while(pl<l[i])del(a[pl++]);
            while(pr>r[i])del(a[pr--]);
            for(int j=nxt[0];j;j=nxt[j])ckmax(ans[i],j*cnt[j]);
        }
        For(i,q)printf("%d\n",ans[i]);
    }
    return 0;
}