MLE 0pts求助!
  • 板块P1001 A+B Problem
  • 楼主lfxxx_
  • 当前回复12
  • 已保存回复13
  • 发布时间2024/8/2 19:27
  • 上次更新2024/8/2 20:49:54
查看原帖
MLE 0pts求助!
795344
lfxxx_楼主2024/8/2 19:27
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=32;
struct balanced_tree{
	int trie[N*M][2],sz[N*M],tot=0;
	void init()
	{
		memset(trie,0,sizeof trie);
		memset(sz,0,sizeof sz);
	} 
	bool find(int x)
	{
		int p=0;
		for(int i=M-1;i>=0;--i)
		{
			int k=(x>>i)&1;
			if(!trie[p][k])
				return 0;
			p=trie[p][k];
		}
		return 1;
	}
	void insert(int x)
	{
		int p=0;
		for(int i=M-1;i>=0;--i)
		{
			int k=(x>>i)&1;
			if(!trie[p][k])
				trie[p][k]=++tot;
			p=trie[p][k];
			++sz[p];
		}
	}
	void erase(int x)
	{
		if(!find(x))
			return ;
		int p=0;
		for(int i=M-1;i>=0;--i)
		{
			int k=(x>>i)&1;
			p=trie[p][k];
			--sz[p];
		}
	}
	int rank(int x)
	{
		int p=0,res=0;
		for(int i=M-1;i>=0;--i)
		{
			int k=(x>>i)&1;
			if(k)
				res+=sz[trie[p][0]];
			p=trie[p][k];
			if(!p)
				break;
		}
		return res;
	}
	int kth(int x)
	{
		int p=0,res=0;
		for(int i=M-1;i>=0;--i)
		{
			if(sz[trie[p][0]]>=x)
				p=trie[p][0]; 
			else
			{
				x-=sz[trie[p][0]];
				res+=(1<<i);
				p=trie[p][1];
			}
		}
		return res;
	}
	int pre(int x){return kth(rank(x));}
	int nxt(int x){return kth(rank(x+1)+1);}
}tr;
int a[N];
int query_rank(int p,int pl,int pr,int L,int R,int k)
{
	if(R<pl||pr<L)
		return 0;
	if(L<=pl&&pr<=R)
	{
		for(int i=pl;i<=pr;++i)
			tr.insert(a[i]);
		int ans=tr.rank(k);
		for(int i=pl;i<=pr;++i)
			tr.erase(a[i]);
		return ans;
	}
	int mid=(pl+pr)>>1;
	return query_rank(p<<1,pl,mid,L,R,k)+query_rank(p<<1|1,mid+1,pr,L,R,k);
}
int query_kth(int p,int pl,int pr,int L,int R,int k)
{
	int l=-1,r=1e9+1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(query_rank(p,pl,pr,L,R,mid)<k)
			l=mid;
		else
			r=mid;
	}
	return l;
}
void update(int p,int d){a[p]=d;}
int query_pre(int p,int pl,int pr,int L,int R,int k)
{
	if(R<pl||pr<L)
		return -2147483647;
	if(L<=pl&&pr<=R)
	{
		for(int i=pl;i<=pr;++i)
			tr.insert(a[i]);
		int ans=tr.pre(k);
		for(int i=pl;i<=pr;++i)
			tr.erase(a[i]);
		return ans;
	}
	int mid=(pl+pr)>>1;
	return max(query_pre(p<<1,pl,mid,L,R,k),query_pre(p<<1|1,mid+1,pr,L,R,k));
}
int query_nxt(int p,int pl,int pr,int L,int R,int k)
{
	if(R<pl||pr<L)
		return 2147483647;
	if(L<=pl&&pr<=R)
	{
		for(int i=pl;i<=pr;++i)
			tr.insert(a[i]);
		int ans=tr.nxt(k);
		for(int i=pl;i<=pr;++i)
			tr.erase(a[i]);
		return ans;
	}
	int mid=(pl+pr)<<1;
	return min(query_nxt(p<<1,pl,mid,L,R,k),query_nxt(p<<1|1,mid+1,pr,L,R,k));
}
int query(int p,int pl,int pr,int L,int R)
{
	if(R<pl||pr<L)
		return 0;
	if(L<=pl&&pr<=R)
	{
		int res=0;
		for(int i=pl;i<=pr;++i)
			res+=a[i];
		return res;
	}
	int mid=(pl+pr)>>1;
	return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
signed main()
{
	int x,y;
	cin>>x>>y;
	update(1,x);
	update(2,y);
	cout<<query_rank(1,1,2,1,1,2)*query_kth(1,1,2,1,1,2)*query_nxt(1,1,2,1,1,2)*query_pre(1,1,2,2,1,2)*1+query(1,1,2,1,2);
}
2024/8/2 19:27
加载中...