题解：P14764 [Opoi 2025] CCD 的不难题

Karmallis · 2026-01-12 21:08:56 · 题解

因为知识不足所以写成了一道极其毒瘤的大模拟+卡常题...

（这件事告诉了我们不要乱飞指针的重要性）

题意

给定一个长为 n 的数列和 q 次询问 (l_i,r_i,k_i)，每次询问求区间 [l,r] 中刚好出现 k 次的数的最大值。

解法

首先我们需要进行分类处理，设出现次数的阈值为 L，那么：

• 对于出现次数 \ge L 的数，其数量必然不会超过 \frac{n}{L} 个，可以直接处理出若干个前缀和数组进行枚举；

• 对于出现次数 < L 的数，可以进行以下操作：

  对于某个特定的出现次数 k，对于数列上的每一个位置的数 a_i，会具有以下参数：前缀 a_i\to{}ll_i，本位 a_i\to{}lr_i，该位后第 k-1 个 a_i\to{}rl_i，该位后第 k 个 a_i\to{}rr_i。我们会发现，对于一个询问 [l,r]，只有当 l\in(ll_i,lr_i]\land{}r\in[rl_i,rr_i)，这个数 a_i 才有可能被选中为答案。

这个判定具有两个偏序参数，因此我们发现对于一个特定的 k，我们其实是在一个二维平面上进行一个矩形修改+单点查询的最大值问题。

因此，我们可以建立 L-1 棵主席树处理这些查询。对于主席树还有一个问题，就是最大值其实是一个不可差分信息，需要多一个 \log；使用一个基数堆（压位 trie）预处理就可以把这个 \log 压掉。

实测 L 取 32 可以通过；注意使用常数较小的写法...

AC Code

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;

const int N=5e4+9,L=32,M=1<<__lg(N)+1,K=M+N;
int n,q,a[N],cnt[N],dyn[N],pre[N],nxt[N],ans;
struct radix_heap{
    ull bmp[8192];
    int cnt[8192][64];
    int hp_sz;
    int size(){
        return hp_sz;
    }
    bool empty(){
        return !hp_sz;
    }
    void insert(int x){
        hp_sz++;
        int u=1;
        int idx=x>>12;
        bmp[u]|=1ull<<idx;
        cnt[u][idx]++;
        u=u<<6|idx;
        x&=4095;
        idx=x>>6;
        bmp[u]|=1ull<<idx;
        cnt[u][idx]++;
        u=u<<6|idx;
        x&=63;
        bmp[u]|=1ull<<x;
        cnt[u][x]++;
    }
    void erase(int x){
        hp_sz--;
        int u=1;
        int idx=x>>12;
        bmp[u]^=1ull<<idx&0ull-!--cnt[u][idx];
        u=u<<6|idx;
        x&=4095;
        idx=x>>6;
        bmp[u]^=1ull<<idx&0ull-!--cnt[u][idx];
        u=u<<6|idx;
        x&=63;
        bmp[u]^=1ull<<x&0ull-!--cnt[u][x];
    }
    int top(){
        if(empty()) return 0; //default is 0
        int u=1;
        u=u<<6|__lg(bmp[u]);
        u=u<<6|__lg(bmp[u]);
        u=u<<6|__lg(bmp[u]);
        return u&262143;
    }
}pq;
vector<unsigned short> ps[N],asn;
bitset<N> vis;
struct node{
    unsigned short ver,val;
    bool state; //0 for sub, 1 for add
    bool operator< (const node& other) const{
        if(ver!=other.ver) return ver<other.ver;
        if(val!=other.val) return val<other.val;
        return state<other.state;
    }
};
vector<node> tr[L][K]; //outer administrates l-set
struct tdl_node{
    int l,r;
    node k;
    bool operator< (const tdl_node& other){
        return k<other.k; //to make sure insertions are ordered
    }
};
vector<tdl_node> tdl[L];
bitset<K> has_val[L];

void insert(int len,int l,int r,node k){
    r++;
    while(l<r){
        int j=min(__builtin_ctz(l),__lg(r-l)); //assume that l is not zero
        auto &at=tr[len][l+M>>j];
        if(!has_val[len][l+M>>j]) at.emplace_back();
        has_val[len][l+M>>j]=1;
        tr[len][l+M>>j].emplace_back(k);
        l+=1<<j;
    }
}
int get_max(int len,int x,int y){
    int res=0;
    for(x+=M;x;x>>=1){
        if(!has_val[len][x]) continue;
        auto it=upper_bound(tr[len][x].begin(),tr[len][x].end(),y,[](int _y,node _x){
            return _y<_x.ver;
        });
        it--;
        res=max(res,(int)it->val);
    }
    return res;
}
void decrypt(vector<int*> v){
    for(auto& at:v) *at^=ans;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    cin>>q;
    for(int i=1;i<=n;i++){ //get pre
        pre[i]=dyn[a[i]];
        dyn[a[i]]=i;
    }
    fill(dyn,dyn+N,n+1);
    for(int i=n;i;i--){ //get nxt
        nxt[i]=dyn[a[i]];
        dyn[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i]]) continue;
        if(cnt[a[i]]>=L){
            vis[a[i]]=1;
            asn.push_back(a[i]);
            ps[a[i]].resize(n+2);
            for(int u=i;u!=n+1;u=nxt[u]) ps[a[i]][u]++;
            partial_sum(ps[a[i]].begin(),ps[a[i]].end(),ps[a[i]].begin());
            continue;
        }
        int len=1;
        for(int u=i;u!=n+1;u=nxt[u]){
            tdl[len].push_back({pre[i]+1,i,{u,a[i],1}}); //right set enter from u
            tdl[len].push_back({pre[i]+1,i,{nxt[u],a[i],0}}); //right set quit from nxt[u]
            len++;
        }
    }
    sort(asn.begin(),asn.end());
    for(int len=1;len<L;len++){
        sort(tdl[len].begin(),tdl[len].end()); //O(Lnlogn)
        for(auto& at:tdl[len]) insert(len,at.l,at.r,at.k);
        tdl[len].clear();
        for(int i=1;i<K;i++){
            if(!has_val[len][i]) continue;
            for(auto& at:tr[len][i]){ //O(Lnlogn)
                if(!at.val) continue;
                if(at.state) pq.insert(at.val); //assume to be O(1)
                else pq.erase(at.val);
                at.val=pq.top();
            }
            auto it=lower_bound(tr[len][i].begin(),tr[len][i].end(),n+1,[](node _x,int _y){
                return _x.ver<_y;
            });
            tr[len][i].erase(it,tr[len][i].end());
        }
    }
    for(int _=1,l,r,k;_<=q;_++){
        cin>>l>>r>>k;
        decrypt({&l,&r,&k});
        ans=0;
        if(k<L){
            ans=get_max(k,l,r);
        }
        int i=asn.size()-1;
        bool flag=1;
        for(;~i&&flag;i--) flag=ps[asn[i]][r]-ps[asn[i]][l-1]!=k;
        if(!flag) ans=max(ans,(int)asn[i+1]);
        cout<<ans<<'\n';
    }
    return 0;
}

复杂度分析

通过调整 L 可以做到时空复杂度 O(n\sqrt{n\log{}n})。