[P6105] [Ynoi2010] y-fast trie 题解

· · 题解

先计算最大加次大减 C，然后变为 \max_{i,j\in S}[i+j<C](i+j)。针对单独一个集合 S，显然有 \mathcal{O}(|S|\log |S|) 做法。

再想想有没有什么性质，注意到 [0,C-1-x] 范围内最大的那个值最有用，可以直接把这个二元组记录下来，如果其中有一个数有了更好的匹配就拆掉这个二元组换成新的，删除也一样重新找一个二元组，但是这样还是不够，因为修改 x 时可能要修改很多个形如 (x,i) 的结构。

再仔细观察发现一个贪心性质。设 s 为 x 的后继，若同时记录了二元组 (s,y)(x,y)，那么 (x,y) 是无用的。再精简一下，设 s 为 \ge x 的第一个有二元组的数，设这个二元组为 (s,y)，则只需要在 [y+1,C-1-x] 范围内找数匹配成二元组即可。

这样就变成时间 \mathcal{O}(n\log n)，空间 \mathcal{O}(n) 了。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=500007,ee=1e18;
struct Node{
    ll x,y,v;
    Node(ll _x,ll _y){x=min(_x,_y),y=max(_x,_y),v=_x+_y;}
    friend bool operator<(Node c,Node o){
        if(c.v==o.v) return c.x<o.x;
        else return c.v>o.v;
    }
};
ll n,C,lstans;
multiset<ll> st;
map<ll,ll> pm;
set<Node> res;
ll qry(void){
    auto it=st.end(); it--;
    auto pre=it; pre--;
    return max(res.begin()->v,*it+*pre-C);
}
void search(multiset<ll>::iterator it,ll x){
    auto suf=pm.upper_bound(x);
    ll lim=0;
    if(suf!=pm.end()) lim=pm[suf->first]+1;
    st.erase(it);
    auto to=st.upper_bound(C-1-x);
    if(to==st.begin()) return st.insert(x),void();
    ll y=*prev(to);
    if(y<lim) return st.insert(x),void();
    if(pm.count(y)){
        ll z=pm[y];
        res.erase(Node(y,z)),pm.erase(z);
    }
    pm[y]=x,pm[x]=y,res.insert(Node{x,y});
    st.insert(x);
}
void addP(ll x){
    st.insert(x);
    auto it=st.find(x);
    if(st.size()>1) search(it,x);
}
void delP(ll x){
    auto it=st.find(x);
    st.erase(it);
    if(pm.count(x)){
        ll y=pm[x];
        pm.erase(x),res.erase(Node{x,y});
        if(x!=y) pm.erase(y);
        if(st.size()>1) search(st.find(y),y);
    }
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>C;
    for(ll i=1,op,x;i<=n;i++){
        cin>>op>>x,x^=lstans,x%=C;
        if(op==1) addP(x);
        else delP(x);
        if(st.size()<2) cout<<"EE\n",lstans=0;
        else cout<<(lstans=qry())<<"\n";
    }
    return 0;
}

::::