CF1476G题解

Ginger_he · 2023-07-22 11:57:15 · 题解

考虑暴力做法，对于 1 操作统计区间内每个数的出现次数 cnt，然后开个桶 p 记录每种出现次数的个数，双指针找到对于每个 i 的最小的 j 使得 j\ge i 且 \sum\limits_{x=i}^jp_x\ge k，答案即为所有的 (i,j) 中 j-i 的最小值，对于 2 操作直接修改即可，时间复杂度 O(n^2)。

考虑优化，发现 \sum\limits_{x=1}^kx=\dfrac{k\times(k+1)}{2}\le n，故使得 p_x 不为 0 的 x 的个数大约只有 O(\sqrt n) 个，所以我们可以维护一个链表，记录 p_x 不为 0 的位置，同时用带修莫队，每次拓展区间就往链表里插数，缩小区间就从链表里删数，然后将链表上的数取出排序后双指针即可，时间复杂度 O(n^{\frac{5}{3}}+n\sqrt n\log n)。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int n,m,len,tmp,s,res,op,x,y,z,u,v,l=1,r,t;
int a[N],lst[N],nxt[N],p[N],cnt[N],f[N],ans[N];
struct query
{
    int l,r,k,t,id;
    bool operator < (const query &x) const
    {
        return l/len==x.l/len?r/len==x.r/len? 
        t<x.t:r<x.r:l<x.l;
    }
}q[N];
struct node
{
    int p,v;
}c[N];
inline void insert(int x)
{
    lst[x]=lst[n+1];
    nxt[x]=n+1;
    nxt[lst[x]]=lst[n+1]=x;
}
inline void erase(int x)
{
    lst[nxt[x]]=lst[x];
    nxt[lst[x]]=nxt[x];
}
inline void add(int x)
{
    p[cnt[x]]--;
    if(!p[cnt[x]]) erase(cnt[x]);
    if(!p[++cnt[x]]) insert(cnt[x]);
    p[cnt[x]]++;
}
inline void del(int x)
{
    p[cnt[x]]--;
    if(!p[cnt[x]]) erase(cnt[x]);
    if(!cnt[x]) return;
    if(!p[--cnt[x]]) insert(cnt[x]);
    p[cnt[x]]++;
}
inline void update(int t,int i)
{
    if(q[i].l<=c[t].p&&c[t].p<=q[i].r)
    {
        del(a[c[t].p]);
        add(c[t].v);
    }
    swap(c[t].v,a[c[t].p]);
}
int main()
{
    scanf("%d%d",&n,&m);
    len=pow(n,0.666);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op&1) scanf("%d",&z),q[++u]=query{x,y,z,v,u};
        else c[++v]=node{x,y};
    }
    sort(q+1,q+u+1);
    nxt[0]=n+1,lst[n+1]=0;
    for(int i=1;i<=u;i++)
    {
        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(t<q[i].t) update(++t,i);
        while(t>q[i].t) update(t--,i);
        tmp=s=0,res=1e9;
        for(int j=nxt[0];j!=n+1;j=nxt[j])
            f[++tmp]=j,s+=p[j];
        if(s<q[i].k)
        {
            ans[q[i].id]=-1;
            continue;
        }
        sort(f+1,f+tmp+1);
        s=0;
        for(int j=1,r=0;j<=tmp;j++)
        {
            while(r<tmp&&s<q[i].k) s+=p[f[++r]];
            if(s<q[i].k) break;
            s-=p[f[j]]; 
            res=min(res,f[r]-f[j]);
        }
        ans[q[i].id]=res;
    }
    for(int i=1;i<=u;i++)
        printf("%d\n",ans[i]);
    return 0;
}