题解：CF1732D2 Balance (Hard version)
cuijiexiong
·
·
题解
思路
为了方便，我们提前离散化。
---
我们先考虑没有删除操作的。
我们用 $S$ 集合记录当且存在的数。
- **加入：** 把数加进 $S$ 里。
- **查询：** 暴力跳，但是我们记忆化一下。具体地，用一个 $tag_i$ 记录这个数跳到的位置，也就是答案为 $tag_i\times x$（$x$ 为查询的数）。
::::info[关于时间复杂度]
这样我们加入时间复杂度为 $O(\log n)$。
对于一个加入集合的数 $x$，发现 $x$ 最多影响**查询值**为**它的约数**的查询，一个数约数的个数为 $O(\log n)$ 的。因为我们做了记忆化，插入的数个数为 $O(n)$，所以总共跳的个数为 $O(n\log n)$。用 set 维护，时间复杂度为 $O(n\log^2 n)$。
::::
---
现在有一个删除操作，意味着我们暴力跳到答案在前面输出了，但可能在后面删掉了一个更小的数，再来一次查询，答案就不是我们跳到值了（你也不可能再从 $1$ 重新跳）。
所以我们要用另一东西维护那些因**删除**产生的答案。
具体的用 $vec_x$ 维护询问 $x$ 时，那些影响查询 $x$ 的答案且被删除的数。
:::info[辅助理解]
已经加入了 $\{1,2,3,4,5\}$。
现在查询 $1$，那么正常的话，$tag_1$ 会跳到 $6$，答案也为 $6$。
然后我们删除 $3$，那么就将 $3$ 加入进 $vec_1$ 里。
再查询一遍 $1$ 时，就先找 $vec_1$ 里的最小值（找到是 $3$，答案就是 $3$），如果没有值再跳 $tag_1$。
:::
删掉后再次加入要把 $x$ 所影响的 $vec$ 中的自己删掉。
所以要用 $ye_x$ 和 $re_x$ 辅助维护：
* $ye_x$ 表示 $x$ 有没有被删过。
* $re_x$ 表示如果 $x$ 删掉所影响的查询。
所以最终操作为：
- **加入：** 加入 $S$，如果删过就把它影响的询问的 $vec$ 中的自己删掉。
- **查询：** 如果 $vec$ 有值，答案就为 $vec$ 的最小值，否则 $tag$ 就暴力跳同时维护 $re_x$。
- **删除：** 给目前 $x$ 删掉会影响的值的 $vec$ 里加入这个 $x$，$S$ 删掉 $x$，更小 $ye_x$。
::::info[关于时间复杂度]
这里讨论是**加入**和**删除**，其他的前面的**关于时间复杂度**讨论了。
加入需要枚举 $re_x$ 的元素，个数是约数个数 $O(\log n)$，$vec$ 用 set 维护，时间复杂度为 $O(\log^2 n)$。
删除同理，就不赘述了。
::::
# 代码
有需要的可以结合代码理解。
```cpp
#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int N=2e5+100;
int n;
char op[N];
ll a[N];
map<ll,int> mp;
ll f[N],tag[N];
bool ye[N];
vector<int> re[N];
set<ll> st,vec[N];//st 即 S
void lsh(){
int tot=0;
for(auto &it:mp)
it.se=++tot,f[tot]=it.fi;
for(int i=1;i<=n;i++)
a[i]=mp[a[i]];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>op[i]>>a[i];
mp[a[i]];
}
lsh(); //拼音意思，离散化。
for(int i=1;i<=n;i++){
if(op[i]=='+'){
st.insert(f[a[i]]);
if(ye[a[i]]){
for(int &it:re[a[i]])
vec[it].erase(f[a[i]]);
}
}
if(op[i]=='-'){
st.erase(f[a[i]]);
for(int &it:re[a[i]])
vec[it].insert(f[a[i]]);
ye[a[i]]=true;
}
if(op[i]=='?'){
if(vec[a[i]].size()){
cout<<*vec[a[i]].begin()<<"\n";
}else{
tag[a[i]]=max(tag[a[i]],1ll);
set<ll>::iterator it;
while((it=st.find(tag[a[i]]*f[a[i]]))!=st.end()){
re[mp[*it]].push_back(a[i]);
tag[a[i]]++;
}
cout<<tag[a[i]]*f[a[i]]<<"\n";
}
}
}
return 0;
}
```