CF 1476G Minimum Difference 题解

zcxxnqwq · 2023-01-10 10:37:07 · 题解

首先它显然需要用带修莫队，问题就是如何求最小极差。

这种出现次数相关的题有一个非常巧妙的性质：\sum\limits_{i=1}^k i=\dfrac{k(k+1)}{2}=n，则不同的出现次数 k 最多是 O(\sqrt n) 级别的，可以进行一些暴力计算。

在做莫队时维护 tong_i 表示有多少个不同的数出现了 i 次，求最小极差那就双指针就行了。但有很多 tong_i=0 的情况不能暴力扫，所以要用一个链表维护 tong_i 有值的位置，在有意义的位置上做双指针。

要注意莫队加入一个数的时候新的值插入链表的哪个位置要分类讨论一下。

#include<bits/stdc++.h>
#define ll long long
#define ff(i,s,e) for(int i=(s);i<=(e);++i)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1e5+5,lim=1e5;
int n,m,a[N],siz,bel[N],cc,cq,ans[N];
struct qwq{
    int l,r,k,t,id;
    bool operator < (const qwq &a) const{
        if(bel[l]!=bel[a.l]) return bel[l]<bel[a.l];
        if(bel[r]!=bel[a.r]) return bel[r]<bel[a.r];
        return t<a.t;
    }
}q[N];
struct qaq{
    int pos,x;
}c[N];
int tong[N],cnt[N],pre[N],nxt[N];
inline void erase(int x){
    nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
}
inline void ins(int pos,int x){
    nxt[x]=nxt[pos],pre[x]=pos,nxt[pos]=x,pre[nxt[x]]=x;
}
inline void add(int x){
    int &tmp=cnt[x];
    --tong[tmp];
    if(!tong[tmp]) erase(tmp);
    ++tmp,++tong[tmp];
    if(tong[tmp]==1) ins(tong[tmp-1]?tmp-1:pre[tmp-1],tmp);
}
inline void del(int x){
    int &tmp=cnt[x];
    --tong[tmp];
    if(!tong[tmp]) erase(tmp);
    --tmp,++tong[tmp];
    if(tong[tmp]==1) ins(pre[tmp+1],tmp);
}
inline void change(int x,int i){
    if(c[x].pos>=q[i].l&&c[x].pos<=q[i].r){
        del(a[c[x].pos]),add(c[x].x);
    }
    swap(a[c[x].pos],c[x].x);
}
signed main(){
    n=read(),m=read(),siz=pow(n,0.66),tong[0]=n+1,nxt[0]=lim+1;
    ff(i,1,n) a[i]=read(),bel[i]=(i+siz-1)/siz;
    ff(i,1,m){
        int op=read(),x=read(),y=read();
        if(op==1) q[++cq]={x,y,read(),cc,cq};
        else c[++cc]={x,y};
    }
    sort(q+1,q+cq+1);
    int l=1,r=0,tim=0;
    ff(i,1,cq){
        while(l>q[i].l) add(a[--l]);
        while(r<q[i].r) add(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        while(tim<q[i].t) change(++tim,i);
        while(tim>q[i].t) change(tim--,i);
        int mn=1e9;  
        for(int l=nxt[0],r=0,sum=0;r<=lim;){
            while(r<=lim&&sum<q[i].k) r=nxt[r],sum+=tong[r];
            while(sum>=q[i].k) mn=min(mn,r-l),sum-=tong[l],l=nxt[l];
        }
        ans[q[i].id]=mn==1e9?-1:mn;
    }
    ff(i,1,cq) printf("%d\n",ans[i]);
    return 0;
}