P6105 [Ynoi2010] y-fast trie

无钩七不改名 · 2025-12-03 19:47:11 · 题解

写个可爱小常数做法。

根据取模的性质，每个输入的 x 先模个 C 再说。

然后我们考虑对于两个数 i 和 j，有两种情况：

• i+j\ge C
• i+j<C

对于第一种情况，最优解显然是最大值和次大值。

对于第二种情况，我们考虑匹配一些数对，存在大根堆里面。每次查找答案的时候如果堆顶数对不存在就踹掉，直到堆空或者找到存在的数对。

具体操作如下：

将每个数都存入 multiset 中，用 map 标记它匹配的数是多少，如果没有匹配的数则为 -1。

设当前的数为 x。

• 对于每个插入操作，我们在 multiset 中查找使得 x+y<C 的最大的 y，如果 y 没有匹配的数或者和 y 匹配的数小于等于 x，匹配 x 和 y，标记并丢入大根堆。否则 x 不做匹配。然后将 x 丢进 multiset。
• 对于每个删除操作，如果 x 有匹配的数，按照插入的方式给这个数重新尝试匹配一个数。然后在 multiset 里面删去这个数。

code:

#include<bits/stdc++.h>
using namespace std;

const int N=500005;

int n,C;
unordered_map<int,int> ump;
multiset<int> s;
priority_queue<pair<int,pair<int,int> > > pq;
int ans;

int read(){
    int f=1,k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        k=k*10+ch-'0';
        ch=getchar();
    }
    return f*k;
} 

int main(){
    n=read();C=read();
    while(n--){
        int op=read(),x=(read()^ans)%C;
        //cout<<"x:"<<x<<'\n';
        if(op==1){
            ump[x]=-1;
            auto it=s.upper_bound(C-x-1);
            if(it!=s.begin()){
                --it;
                int y=ump[*it];
                if(y<=x||s.find(y)==s.end()){
                    //cout<<x<<"<->"<<*it<<'\n';
                    ump[x]=*it;
                    ump[*it]=x;
                    pq.push({x+*it,{x,*it}});
                }
            }
            s.insert(x);
        }
        else{
            s.erase(s.find(x));
            int z=ump[x];
            if(s.find(z)!=s.end()){
                ump[z]=-1;
                s.erase(s.find(z));
                auto it=s.upper_bound(C-z-1);
                if(it!=s.begin()){
                    --it;
                    int y=ump[*it];
                    if(y<=z||s.find(y)==s.end()){
                        //cout<<x<<"<->"<<*it<<'\n';
                        ump[z]=*it;
                        ump[*it]=z;
                        pq.push({z+*it,{z,*it}});
                    }
                }
                s.insert(z);
            }
        }
        if(s.size()<2){
            puts("EE");
            ans=0;
        }
        else{
            auto it=s.end();
            --it;
            ans=*it;
            --it;
            ans+=*it;
            //cout<<"ans1:"<<ans<<'\n';
            if(ans>=C)ans-=C;
            int res=0;
            while(pq.size()){
                pair<int,int> pr=pq.top().second;
                //cout<<pr.first<<" "<<pr.second<<" "<<ump[pr.first]<<" "<<ump[pr.second]<<'\n';
                if(s.find(pr.first)==s.end()||s.find(pr.second)==s.end())pq.pop();
                else if(pr.first==pr.second&&s.count(pr.second)==1)pq.pop();
                else{
                    res=pr.first+pr.second;
                    break;
                }
            }
            ans=max(res,ans);
            printf("%d\n",ans);
        }
    }
    return 0;
}

感谢@waauto 的 debug。