社区讨论

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 条回复,欢迎继续交流。

正在加载回复...