社区讨论
RE on Sub4 81pts 求条 选两关
P6105[Ynoi2010] y-fast trie参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mjbeb1r5
- 此快照首次捕获于
- 2025/12/18 20:07 2 个月前
- 此快照最后确认于
- 2025/12/20 19:15 2 个月前
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
multiset<ll> s;
map<ll,ll> mp;
priority_queue<pair<ll,pair<ll,ll> > > q;
ll n,C;
void ins(ll val) {
val=val%C;
auto it=s.upper_bound(C-val-1);
if(it==s.begin()) {
mp[val]=-1;
s.insert(val);
return;
}
ll pr=*--it;
ll pre=mp[pr];
if(pre<=val||s.find(pre)==s.end()) mp[val]=pr,mp[pr]=val,q.push({pr+val,{val,pr}});
s.insert(val);
}
void del(ll val) {
val=val%C;
s.erase(s.find(val));
ll pr=mp[val];
if(s.find(pr)!=s.end()) {
mp[pr]=-1;
s.erase(s.find(pr));
ins(pr);
}
}
ll qry() {
if(s.size()<2) return -1;
else {
auto it=s.end();
ll ans1=*--it;//max
ans1+=*--it;//smax
if(ans1>=C) ans1-=C;
ll ans2=-1;
while(q.size()) {
pair<ll,ll> sd=q.top().second;
if(s.find(sd.first)==s.end()||s.find(sd.second)==s.end()) q.pop();
else {
ans2=sd.first+sd.second;
break;
}
}
return max(ans1,ans2);
}
}
ll opt,x,lst;
int main() {
cin>>n>>C;
for(int i=1;i<=n;i++) {
scanf("%lld %lld",&opt,&x);
x^=lst;
if(opt==1) ins(x);
else del(x);
lst=qry();
if(lst==-1) {
lst=0;
printf("EE\n");
} else printf("%lld\n",lst);
}
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...