【题解】 CF1732 D2

· · 题解

蒟蒻的第一篇题解

调了2h+的动态开点线段树被赛后10min写完的set瞎搞做法给吊打了

Description

维护一个集合 S ，有三种操作：插入一个数、删除一个数、查询 k 的倍数中没出现过的最小的数。

Solution

本来想写动态开点线段树维护，后来发现用 set 瞎搞就能解决。

对于一个修改操作 x ,它有可能影响到哪些询问 k 呢？显然当 k 是 x 的因数时就有可能影响到。所以我们可以维护以下三个集合：

  1. 集合 S 就是题目中的集合。

  2. 集合 S1[k] 维护对于每个 k ， k 的倍数中“可能”在集合 S 中没出现的数的集合（就是有可能成为答案的集合）。

  3. 集合 S2[k] 维护每一个数的因子的集合。这里有一个小技巧，如果我们如果维护每个数的所有因子的话时间肯定会炸，但我们只要维护那些有可能询问到的因子就行了，一边询问一边维护 S2 即可

具体地，对于插入操作，直接在 S 中插入即可；

对于删除操作，先在 S 中把这个数 x 删掉，然后再在 x 的所有因子的 S1 中插入 x ；

对于询问 k ， 直接在 k 的 S1 中暴力跳，直到有一个数满足在 S 中没有出现然后输出就行了,顺便在这个过程中维护一下 S2

还有一个细节，因为数据范围很大，所以要用 map 代替普通的数组

具体实现看代码吧 （其实还挺短的）

Code

#define int long long

int q;
set <int> S;//题目中的集合s
map <int,set<int> >disapr,factor;
//disapr维护对每个k,k的倍数中"可能"没出现过的数
//factor维护每个x的因数，一边修改一边维护，只记录有用的就行
signed main(){
    cin>>q;
    while(q--){
        char opt;int x;
        cin>>opt>>x;
        if(opt=='+') S.insert(x);
        else if(opt=='-'){
            S.erase(x);
            set <int> ::iterator it=factor[x].begin();
            while(it!=factor[x].end()) disapr[*it].insert(x),it++;
        }else{
            disapr[x].insert(x);
            int u=*disapr[x].begin();
            factor[u].insert(x);
            while(S.count(u)){
                disapr[x].erase(u);
                if(disapr[x].empty()) disapr[x].insert(u+x);
                u=*disapr[x].begin(),factor[u].insert(x);
            }
            cout<<*disapr[x].begin()<<endl;
        }
    }
    return 0;
}

暴力跳的复杂度本蒟蒻也不会算，可能是倒数之和均摊一下就变成 O(qlogX) 了？反正能过