crz_qwq @ 2024-08-03 09:21:33
#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);
}
by cyq111111 @ 2024-10-25 11:30:39
@TianHaolin 望丰展,使MD
by cyq111111 @ 2024-10-25 11:31:29
md
by cyq111111 @ 2024-10-25 11:38:44
@TianHaolin 希望更丰富的展现?使用 Markdown