专栏文章

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

aaeiouaoeiu
P6105题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4s0c7
此快照首次捕获于
2025/12/01 20:33
3 个月前
此快照最后确认于
2025/12/01 20:33
3 个月前
查看原文
先计算最大加次大减 CC，然后变为 max⁡i,j∈S[i+j<C](i+j)\max_{i,j\in S}[i+j<C](i+j)。针对单独一个集合 SS，显然有 O(∣S∣log⁡∣S∣)\mathcal{O}(|S|\log |S|) 做法。
再想想有没有什么性质，注意到 [0,C−1−x][0,C-1-x] 范围内最大的那个值最有用，可以直接把这个二元组记录下来，如果其中有一个数有了更好的匹配就拆掉这个二元组换成新的，删除也一样重新找一个二元组，但是这样还是不够，因为修改 xx 时可能要修改很多个形如 (x,i)(x,i) 的结构。
再仔细观察发现一个贪心性质。设 ss 为 xx 的后继，若同时记录了二元组 (s,y)(x,y)(s,y)(x,y)，那么 (x,y)(x,y) 是无用的。再精简一下，设 ss 为 ≥x\ge x 的第一个有二元组的数，设这个二元组为 (s,y)(s,y)，则只需要在 [y+1,C−1−x][y+1,C-1-x] 范围内找数匹配成二元组即可。
这样就变成时间 O(nlog⁡n)\mathcal{O}(n\log n)，空间 O(n)\mathcal{O}(n) 了。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...