[UOI 2026] mex plus

首先有一个 trick,即把 \(x,y\) 分别放到 \(A,B\) 集合里面可以在图上对 \((x,y)\) 建一条边，选择的过程可以转化为给边定向的过程，令 \(x\to y\)，表示 \(x\) 放入 \(A\)，\(y\) 放入 \(B\)，反之同理。

题意转化为，最大化最小的出度为零的点和最小的入度为零的点的和，我们考虑先最大化前者，在使前者最大的同时最大化后者。

考虑最大化出度为零的点，发现对于图的不同形态贡献不同。首先是无环的连通块，即一棵树，发现我们无论怎么定向都至少有一个点出度为零即树根，处理方式就是使编号最大的点为树根，这样其他点都会在 \(A\) 集合中出现，此时 \(B\) 中包含了除叶子节点以外的点。

考虑有环的连通块，发现一个环上所有点都可以加入两个集合，那么要最大化最小的出度为零的点的编号的话，我们只要让所有边都向环的方向，这样不会有任何点出度为零，而入度为零的同样是叶子节点。

那此时答案就是所有树连通块的最大编号中的最小值，加上所有叶子节点中编号最小值，注意重边和自环都算做独立的边。

我们可以并查集维护连通性，堆维护所有无环连通块的最大编号的最小值，注意加边的时候判断是否合并后的集合还是无环的，我们可以给并查集记录一个 pair 类型的 \(w_x\)，第一项表示这个集合中非树边的数量，第二项则表示集合中最大的编号。求叶子节点的最小值则也用一个堆，加上一个数组维护度数就行了。

那我们要动态地删除和加入怎么办呢，套一层线段树分治把删除变为撤销就行了，并查集改成可撤销并查集，堆改为 可删堆。

注意离散化。

时间复杂度 \(O(n\log n\log n)\)。

#include
using namespace std;
#define LL long long
#define _int __int128
#define ull unsigned long long
#define pii pair
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcountll(x)
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rof(i,r,l) for(int i=r;i>=l;i--)
#define endl '\n'
int n,m,tot;
const int N = 3e5+10,V=2e6;
struct node{int u,v;
};
struct que{pq,greater >x,y;void push(int v){x.push(v);}void del(int v){y.push(v);}int top(){while(y.size()&&x.top()==y.top()){y.pop();x.pop();}return x.top();}void pop(){while(y.size()&&x.top()==y.top()){x.pop();y.pop();}x.pop();}
}s;struct dsu{int fa[V],siz[V];vectorw;que q;stack >st;int find(int x){return x==fa[x]?x:find(fa[x]);}void merge(int x,int y){x=find(x),y=find(y);if(x==y){++w[x].fst;if(w[x].fst==1){q.del(w[x].scd);}st.push({x,y,w[x]});return;}if(siz[x]>siz[y])swap(x,y);if(!w[x].fst)q.del(w[x].scd);if(!w[y].fst)q.del(w[y].scd);st.push({x,y,w[y]});fa[x]=y;siz[y]+=siz[x];w[y].fst+=w[x].fst;w[y].scd=max(w[y].scd,w[x].scd);if(!w[y].fst)q.push(w[y].scd);}void back(){auto [x,y,v]=st.top();st.pop();if(x==y){if(!--w[x].fst)q.push(w[x].scd);}else{if(!w[y].fst)q.del(w[y].scd);fa[x]=x;siz[y]-=siz[x];w[y]=v;if(!w[x].fst)q.push(w[x].scd);if(!w[y].fst)q.push(w[y].scd);}}
}d;
vectortr[N<<2];
#define ls p<<1
#define rs p<<1|1
void change(int p,int l,int r,int ql,int qr,node x){if(ql<=l&&r<=qr){tr[p].push_back(x);return;}int mid=(l+r)/2;if(ql<=mid)change(ls,l,mid,ql,qr,x);if(qr>mid)change(rs,mid+1,r,ql,qr,x);
}
map >mp;
int a[N<<1],b[N<<1],lst[N<<1],fna[N<<1],lsh[V],len,du[V];
LL ans[N];
void upd(int x,int v){int val=lsh[x];if(du[x]<2)s.del(val);du[x]+=v;if(du[x]<2)s.push(val);
}
void query(int p,int l,int r){int o=d.st.size();for(auto [u,v]:tr[p]){d.merge(u,v);upd(u,1);upd(v,1);}int mid=(l+r)/2;if(l==r){ans[l]=d.q.top()+s.top();}else{query(ls,l,mid);query(rs,mid+1,r);}for(auto [u,v]:tr[p]){upd(u,-1);upd(v,-1);}while(d.st.size()>o){d.back();}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;fo(i,1,n){cin>>a[i]>>b[i];lsh[++len]=a[i];lsh[++len]=b[i];mp[{a[i],b[i]}].push_back(++tot);fna[i]=-1;}fo(i,1,m){char op;int x,y;cin>>op>>x>>y;if(op=='+'){++tot;a[tot]=x,b[tot]=y;lsh[++len]=x;lsh[++len]=y;mp[{x,y}].push_back(tot);lst[tot]=i;fna[tot]=-1;}else{int id=mp[{x,y}].back();fna[id]=i-1;mp[{x,y}].pop_back();}}fo(i,0,n+m){lsh[++len]=i;}sort(lsh+1,lsh+1+len);len=unique(lsh+1,lsh+1+len)-lsh-1;d.w.resize(len+10);fo(i,1,len){d.fa[i]=i;d.siz[i]=1;d.w[i].fst=0;d.w[i].scd=lsh[i];d.q.push(lsh[i]);s.push(lsh[i]);}fo(i,1,tot){if(fna[i]==-1)fna[i]=m;a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;b[i]=lower_bound(lsh+1,lsh+1+len,b[i])-lsh;change(1,0,m,lst[i],fna[i],(node){a[i],b[i]});}query(1,0,m);fo(i,0,m){cout<