CF1476G 题解

· · 题解

带修莫队

看一眼题面，区间查询还要维护数字出现次数，自然想到莫队，看到单点修改，又能想到带修莫队。

关于每一种数字 cnt 有一个很优秀的性质，就是它的种类数即数字种类数的种类数不会超过 O(\sqrt n)，于是我们可以基于 cnt 的种类数设计暴力算法，当 cnt 单调上升时，我们可以使用双指针解决，至于如何保持有序，我们可以用链表维护，链表下标设为 cnt，每次将链表拍扁成数组排序即可。

时间复杂度 O(n^{\frac{5}{3}}+n \sqrt n\log )。

AC CODE

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int ans=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ans=(ans<<1)+(ans<<3)+ch-'0';
        ch=getchar();
    }
    return w*ans;
}

int n,m;
int a[1000005];
struct query{
    int l;
    int r;
    int t;
    int k;
    int id;
    int ans;
}q[1000005];
int S;
bool cmp(query a,query b){
    if(a.l/S!=b.l/S)return a.l<b.l;
    if(a.r/S!=b.r/S)return a.r<b.r;
    return a.t<b.t;
}
bool cmp1(query a,query b){
    return a.id<b.id;
}
struct modify{
    int p;
    int x;
}mo[1000005];
int cnt1,cnt2;
int l,r,tim;
int cnt[1000005];
int head;
struct node{
    int lst;
    int nxt;
    int val;
}lis[1000005];
struct by{
    int cnt;
    int val;
    bool operator<(const by &a)const{
        return cnt<a.cnt;
    }
}by[1000005];
inline void del_node(int x){
    if(x==head){
        head=lis[x].nxt;
        lis[x]={0,0,0};
        return;
    }
    else{
        lis[lis[x].lst].nxt=lis[x].nxt;
        lis[lis[x].nxt].lst=lis[x].lst;
        lis[x]={0,0,0};
    }
}
inline void add_node(int x){
    lis[x].nxt=head;
    lis[head].lst=x;
    lis[x].val=1;
    head=x;
}

inline void add(int x){
    if(lis[cnt[a[x]]].val>=2){
        lis[cnt[a[x]]].val--;
    }else if(cnt[a[x]]){
        del_node(cnt[a[x]]);
    }
    cnt[a[x]]++;
    if(lis[cnt[a[x]]].val){
        lis[cnt[a[x]]].val++;
    }else if(cnt[a[x]]){
        add_node(cnt[a[x]]);
    }
}
inline void del(int x){
    if(lis[cnt[a[x]]].val>=2){
        lis[cnt[a[x]]].val--;
    }else if(cnt[a[x]]){
        del_node(cnt[a[x]]);
    }
    cnt[a[x]]--;
    if(lis[cnt[a[x]]].val){
        lis[cnt[a[x]]].val++;
    }else if(cnt[a[x]]){
        add_node(cnt[a[x]]);
    }
}
inline void move_t1(){
    ++tim;
    if(mo[tim].p>=l&&mo[tim].p<=r){
        del(mo[tim].p);
        swap(a[mo[tim].p],mo[tim].x);
        add(mo[tim].p);
    }
    else{
        swap(a[mo[tim].p],mo[tim].x);
    }
}
inline void move_t2(){
    if(mo[tim].p>=l&&mo[tim].p<=r){
        del(mo[tim].p);
        swap(a[mo[tim].p],mo[tim].x);
        add(mo[tim].p);
    }
    else{
        swap(a[mo[tim].p],mo[tim].x);
    }
    --tim;
}
int main(){
    n=read();
    m=read();
    S=pow(n,0.6666);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=m;i++){
        int opt=read();
        if(opt==1){
            int l=read(),r=read(),k=read();
            q[++cnt2]={l,r,cnt1,k,i};
        }else{
            int p=read(),k=read();
            mo[++cnt1]={p,k};
        }
    }
    sort(q+1,q+1+cnt2,cmp);
    l=r=1;
    add(1);
    for(int i=1;i<=cnt2;i++){
        while(tim<q[i].t)move_t1();
        while(tim>q[i].t)move_t2();
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(l<q[i].l)del(l++);
        while(r>q[i].r)del(r--);
        int top=0;
        for(int j=head;j;j=lis[j].nxt){
            by[++top]={j,lis[j].val};
        }
        sort(by+1,by+top+1);
        int L=1,R=1;
        int sum=by[1].val;
        int minn=1e9;
        if(sum>=q[i].k)minn=min(minn,0);
        while(R<=top&&L<=top){
            while((sum<q[i].k&&R<top)||(R<L)){
                R++;
                sum+=by[R].val;
            }
            if(sum<q[i].k)break;
            minn=min(minn,by[R].cnt-by[L].cnt);
            sum-=by[L].val;
            L++;
        }
        q[i].ans=minn==1e9?-1:minn;
    }
    sort(q+1,q+1+cnt2,cmp1);
    for(int i=1;i<=cnt2;i++){
        printf("%d\n",q[i].ans);
    }
}