题解：AT_abc356_f [ABC356F] Distance Component Size Query

Hope888 · 2024-07-29 10:46:00 · 题解

明显可以分别二分往 x 两边跳的答案。二分的 Check 可以通过区间询问差距的最大值是否超过 k 来判断。

而对于区间的询问，使用线段树，先离线从小到大分配线段树每个叶子对应哪个数，修改结点时把线段树叶子上的布尔标记取反，难点就只剩 pushup 了。

    node pushup(node x,node y)
    {
        node ans={x.tot+y.tot,0,0,0};
        if(x.tot==0||y.tot==0)//如果有一边没有节点，则直接用另一边
        {
            if(x.tot==0)ans.res=y.res;
            else if(y.tot==0)ans.res=x.res;
        }
        else ans.res=max(max(x.res,y.res),abs(x.rnum-y.lnum));//用两段答案和中间更新最大值
        if(x.tot==0)ans.lnum=y.lnum;
        else ans.lnum=x.lnum;
        if(y.tot==0)ans.rnum=x.rnum;
        else ans.rnum=y.rnum;
        return ans;
    }

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int q,k;
struct node
{
    int tot,res,lnum,rnum;
};
unordered_map<long long,int>id;
struct que
{
    int op,x,idx;
}t[N];
bool cmp1(que x,que y)
{
    return x.x<y.x;
}
bool cmp2(que x,que y)
{
    return x.idx<y.idx;
}
struct tree
{
    #define lson l,mid,num<<1
    #define rson mid+1,r,num<<1|1
    #define get_mid int mid=(l+r)>>1
    node a[N<<2];
    node pushup(node x,node y)
    {
        node ans={x.tot+y.tot,0,0,0};
        if(x.tot==0||y.tot==0)
        {
            if(x.tot==0)ans.res=y.res;
            else if(y.tot==0)ans.res=x.res;
        }
        else ans.res=max(max(x.res,y.res),abs(x.rnum-y.lnum));
        if(x.tot==0)ans.lnum=y.lnum;
        else ans.lnum=x.lnum;
        if(y.tot==0)ans.rnum=x.rnum;
        else ans.rnum=y.rnum;
        return ans;
    }
    void build(int l,int r,int num)
    {
        if(l==r)
        {
            a[num]={0,0,0,0};
            return;
        }
        get_mid;
        build(lson),build(rson);
        a[num]=pushup(a[num<<1],a[num<<1|1]);
    }
    void update(int pos,int x,int l,int r,int num)
    {
        if(l==r&&l==pos)
        {
            a[num]={!a[num].tot,0,x,x};
            return;
        }
        get_mid;
        if(pos<=mid)update(pos,x,lson);
        if(pos>mid)update(pos,x,rson);
        a[num]=pushup(a[num<<1],a[num<<1|1]);
    }
    node query(int L,int R,int l,int r,int num)
    {
        if(L<=l&&r<=R)return a[num];
        get_mid;
        if(L<=mid&&R>mid)return pushup(query(L,R,lson),query(L,R,rson));
        if(L<=mid)return query(L,R,lson);
        if(R>mid)return query(L,R,rson);
    }
}tr;
signed main()
{
    cin>>q>>k;
    int tot=0;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i].op>>t[i].x;
        t[i].idx=i;
    }
    sort(t+1,t+1+q,cmp1);
    for(int i=1;i<=q;i++)
    {
        if(t[i].op==2)continue;
        if(!id.count(t[i].x))id[t[i].x]=++tot;
    }
    sort(t+1,t+1+q,cmp2);
    tr.build(1,tot,1);
    for(int i=1;i<=q;i++)
    {
        if(t[i].op==1)tr.update(id[t[i].x],t[i].x,1,tot,1);
        else
        {
            int ans1=0,ans2=0,l=id[t[i].x],r=tot;
            while(l<=r)
            {
                int mid=l+r>>1;
                node tt=tr.query(id[t[i].x],mid,1,tot,1);
                if(tt.res<=k)
                {
                    ans1=tt.tot;
                    l=mid+1;
                }
                else r=mid-1;
            }
            l=1,r=id[t[i].x];
            while(l<=r)
            {
                int mid=l+r>>1;
                node tt=tr.query(mid,id[t[i].x],1,tot,1);
                if(tt.res<=k)
                {
                    ans2=tt.tot;
                    r=mid-1;
                }
                else l=mid+1;
            }
            cout<<ans1+ans2-1<<endl;
        }
    }
}