P6105 y-fast trie

题面

原题链接 click

题解

可以插入删除时先对 \(C\) 取模，不难发现这不会影响答案。
考虑什么时候能取到最优？一种情形是尽可能接近 \(2C\)，另一种是接近 \(C\) 但小于 \(C\)。
前面一种非常容易处理，直接取较大的两个相加即可。
后面一种的话，我们为每个数寻找一个最优匹配数，这样就能较为方便地统计答案。
但仍然有一个问题：如果一个数是大量数地最优匹配数，那么对它的修改会带来巨大的复杂度。
那我们考虑维护一种双向的最优匹配关系，就是只维护 \((u,v)\) 满足 \(u,v\) 分别是对方的最优匹配数。这样就能实现快速插入。
然后删除的话就考虑有没有匹配，没有就直接删，有的话就把两个一起删，再把另外一个加回去即可。
细节较多，实现需谨慎。
使用 \(\mathrm{set}\) 维护，复杂度 \(O(n\log n)\)。

Code

#include<bits/stdc++.h>
using namespace std;
int p;
struct node{
    int u,v;
    bool operator<(const node &b)const{
        if(u!=b.u) return u<b.u;
        return v<b.v;
    }
};
multiset<node>d;
multiset<int>ans;
void add(int u){
    u%=p;
    node s={u,-1};
    if(d.empty()){
        d.insert(s); return;
    }
    multiset<node>::iterator it=d.lower_bound(node{p-u,-1});
    if(it==d.begin()){
        d.insert(s); return;
    }
    it--;
    if((it->u+u)<p&&it->v==-1||(it->u+it->v)<(it->u+u)){
        if(it->v!=-1){
            multiset<node>::iterator x=d.lower_bound(node{it->v,it->u});
            node xx=*x; d.erase(x); xx.v=-1; d.insert(xx);
            ans.erase(ans.lower_bound(it->u+it->v));
        }
        node tmp=*it; d.erase(it); tmp.v=u; d.insert(tmp); s.v=tmp.u; d.insert(s);
        ans.insert(s.u+s.v);
    }else{
        d.insert(s);
    }
}
void del(int u){
    u%=p;
    multiset<node>::iterator it=d.lower_bound(node{u,-1});
    if(it->v==-1){
        d.erase(it); return;
    }
    node w=*it; d.erase(it);
    multiset<node>::iterator s=d.lower_bound({w.v,w.u});
    ans.erase(ans.lower_bound(w.u+w.v));
    d.erase(s);
    add(w.v);
}
int getans(){
    if(d.size()<2) return -1;
    int h=0;
    multiset<node>::iterator x=d.end(); x--; h+=x->u; x--; h+=x->u; h%=p;
    if(!ans.empty()){
        multiset<int>::iterator it=ans.end(); it--;
        h=max(h,*it);
    }
    return h;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int q,lastans=0; cin>>q>>p; while(q--){
        int tp,x; cin>>tp>>x;
        x^=lastans;
        if(tp==1){
            add(x);
        }else{
            del(x);
        }
        int ans=getans();
        if(ans==-1) cout<<"EE\n";
        else cout<<ans<<'\n';
        lastans=max(ans,0);
    }
    return 0;
}