CF1418D 题解

ikunTLE · 2025-09-14 18:00:11 · 题解

思路

首先考虑如果没有修改操作该怎么做。不难想到可以在间隔最大的两堆中间一分为二，左边的垃圾堆成一堆，右边的垃圾堆成一堆。

设最左边和最右边垃圾的距离为 S，间隔最大的两堆垃圾的间隔为 M，则答案为 S-M。

如何维护 S：可以使用一个 set 进行维护垃圾堆的最大值和最小值，相减得到 S。

如何维护 M：可以使用 map 或者 multiset 来维护每两个垃圾堆之间的间隔，同样可以查询其最大值。（下文中用统一用 map 表示）

移除操作：先判断该操作是否会改变最大值或最小值，进而改变 S 的值。然后可以从 set 中移除该元素，同时在 map 中移除该垃圾堆距离两侧的距离并添加一个大距离。

添加操作：特判同上，后面的操作也都是移除操作的逆操作。

注意事项

• 如果你维护 M 的值时使用了 multiset，删除元素时需要删除指针而不是元素的值，因为 multiset 中重复元素时删除元素的值会将所有该值的信息全部删除。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
int p[N];
#define sum (*(--s.end())-*s.begin())
int main(){
    int n=read(),Q=read();
    set<int>s;
    for(int i=1;i<=n;++i){
        p[i]=read();
        s.insert(p[i]);
    }
    sort(p+1,p+n+1);
    map<int,int>mp;
    for(int i=2;i<=n;++i)
        ++mp[p[i]-p[i-1]];
    while(Q--){
        if(s.size()<=2)
            printf("0\n");
        else{
            auto newit=--mp.end();
            printf("%d\n",sum-(*newit).first);
        }
        int op=read(),x=read();
        if(!op){
            if(s.size()<=2){
                mp.clear();
                s.erase(x);
                continue;
            }
            auto it=s.lower_bound(x);
            auto lit=it,rit=it;
            --lit,++rit;
            if(rit==s.end()){
                int val=*it-*lit;
                --mp[val];
                if(!mp[val])
                    mp.erase(val);
            }
            else if(it==s.begin()){
                int val=*rit-*it;
                --mp[val];
                if(!mp[val])
                    mp.erase(val);
            }
            else{
                int val=*rit-*lit,val1=*rit-*it,val2=*it-*lit;
                ++mp[val],--mp[val1],--mp[val2];
                if(!mp[val1])
                    mp.erase(val1);
                if(!mp[val2])
                    mp.erase(val2);
            }
            s.erase(it);
        }
        else{
            if(s.empty()){
                s.insert(x);
                continue;
            }
            if(x<*s.begin()){
                int val=*s.begin();
                ++mp[val-x];
                s.insert(x);
                continue;
            }
            if(x>*(--s.end())){
                int val=*(--s.end());
                ++mp[x-val];
                s.insert(x);
                continue;
            }
            s.insert(x);
            auto it=s.lower_bound(x);
            auto lit=it,rit=it;
            --lit,++rit;
            int val=*rit-*lit,val1=*rit-*it,val2=*it-*lit;
            --mp[val],++mp[val1],++mp[val2];
            if(!mp[val])
                mp.erase(val);
        }
    }
    if(s.size()<=2)
        printf("0\n");
    else{
        auto newit=--mp.end();
        printf("%d\n",sum-(*newit).first);
    }
    return 0;
}