线段树

考虑 $k$-负载的本质：编号最小的长度不小于 $k$ 的空段。

最初的 $n$ 个元素把序列切割成 $O(n)$ 个空段，使用 set 维护这些空段，记录空段的左右端点。注意加入一个长度为 $\inf$ 的段处理右边界。插入和删除元素的操作只会影响到 $O(1)$ 个空段。加入元素要么将一个空段切割为两个空段，要么缩短一个空段的某个端点，要么删除一个空段。删除元素的情况相反。

维护一个能够查询给定区间是否已经被覆盖的 set 记录所有空段，具体操作如下。

struct Segment{int l,r;Segment(int x,int y):l(x),r(y){}};
bool cmp(const Segment &x,const Segment &y){return x.r<y.l;}
set<Segment,decltype(&cmp)> s(cmp);

因为 set 在 $x<y$ 为假且 $y<x$ 为假时将元素判等，所以可以使用 s.find(Segment(l,r)) 逐个找到所有与 $[l,r]$ 相交的区间，本题中只会寻找一个点，非常容易维护。注意特判对 $1$ 的删除操作，因为 $1$ 左边不存在任何元素。

使用动态开点线段树维护长度在区间 $[l,r]$ 内的线段的最小编号用来回答询问。

由于 $n,m$ 同阶，时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int inf=4'000'000;
struct Segment{int w,ls,rs;set<int> s;}s[200'005*25];
struct Line{int l,r;Line(int x,int y):l(x),r(y){}};
bool cmp(const Line &x,const Line &y){return x.r<y.l;}
set<Line,decltype(&cmp)> v(cmp);
int n,m,ro,seg;
set<int> w;
void update(int &u,int l,int r,int p,int k){
    if(u==0) u=++seg;
    if(l==r){
        auto it=s[u].s.find(k);
        if(it!=s[u].s.end()) s[u].s.erase(it);
        else s[u].s.emplace(k);
        if(s[u].s.empty()) s[u].w=inf;
        else s[u].w=*s[u].s.begin();
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p,k);
    else update(s[u].rs,mid+1,r,p,k);
    s[u].w=min(s[s[u].ls].w,s[s[u].rs].w);
}
int query(int u,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return s[u].w;
    int ret=inf,mid=(l+r)>>1;
    if(ql<=mid) ret=min(ret,query(s[u].ls,l,mid,ql,qr));
    if(qr>mid) ret=min(ret,query(s[u].rs,mid+1,r,ql,qr));
    return ret;
}
void addpoint(int x){
    auto it=*v.find(Line(x,x));
    w.emplace(x);
    update(ro,1,inf,it.r-it.l+1,it.l);
    v.erase(it);
    if(it.l==it.r) return;
    if(x==it.l||x==it.r){
        it.l+=(x==it.l),it.r-=(x==it.r);
        update(ro,1,inf,it.r-it.l+1,it.l);
        v.emplace(it);
    }
    else{
        update(ro,1,inf,(x-1)-it.l+1,it.l);
        v.emplace(Line(it.l,x-1));
        update(ro,1,inf,it.r-(x+1)+1,x+1);
        v.emplace(Line(x+1,it.r));
    }
}
void delpoint(int x){
    auto l=w.find(x-1),r=w.find(x+1);
    w.erase(x);
    if(x!=1&&l==w.end()&&r==w.end()){
        auto itl=*v.find(Line(x-1,x-1)),itr=*v.find(Line(x+1,x+1));
        update(ro,1,inf,itl.r-itl.l+1,itl.l);
        v.erase(itl);
        update(ro,1,inf,itr.r-itr.l+1,itr.l);
        v.erase(itr);
        update(ro,1,inf,itr.r-itl.l+1,itl.l);
        v.emplace(Line(itl.l,itr.r));
    }
    else if(x!=1&&l==w.end()||r==w.end()){
        auto it=*v.find(x!=1&&l==w.end() ? Line(x-1,x-1):Line(x+1,x+1));
        update(ro,1,inf,it.r-it.l+1,it.l);
        v.erase(it);
        it.l-=(r==w.end()),it.r+=(x!=1&&l==w.end());
        update(ro,1,inf,it.r-it.l+1,it.l);
        v.emplace(it);
    }
    else{
        update(ro,1,inf,1,x);
        v.emplace(Line(x,x));
    }
}
void solution(){
    cin>>n,w.clear(),v.clear();
    for(int i=1;i<=seg;i++) s[i].w=0,s[i].ls=0,s[i].rs=0,s[i].s.clear();
    ro=0,seg=0,s[0].w=inf;
    update(ro,1,inf,inf,1);
    v.emplace(Line(1,inf));
    for(int i=1;i<=n;i++){
        static int x;
        cin>>x,addpoint(x);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        static char opt;
        static int x;
        cin>>opt>>x;
        if(opt=='?') cout<<query(ro,1,inf,x,inf)<<' ';
        else if(opt=='+') addpoint(x);
        else if(opt=='-') delpoint(x);
    }
    cout<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}