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 juruo5e59 @ 2024-08-03 09:29:15
@crz_qwq 帮你改了一下AC了(doge
#include <bits/stdc++.h>
int main(){int a,b;std::cin>>a>>b;std::cout<<a+b;return 0;}by TianHaolin @ 2024-08-03 16:11:14
1
by TianHaolin @ 2024-08-03 16:31:51
using namespace std; const int N=1e5+10; int a[N]; long long n,q,x,s=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); cin>>q; for(int i=1;i<=q;i++) { x=0; cin>>x; cout<<upper_bound(a+1,a+1+n,x)-a-1<<endl; } }1. ```cpp
using namespace std; const int N=1e5+10; int a[N]; long long n,q,x,s=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); cin>>q; for(int i=1;i<=q;i++) { x=0; cin>>x; cout<<upper_bound(a+1,a+1+n,x)-a-1<<endl; } }
by TianHaolin @ 2024-08-04 14:22:23
1
by xQWQx @ 2024-08-05 15:44:36
@TianHaolin ?
by AK_AK_AK @ 2024-08-05 20:27:30
1+1=3
by Kristeen @ 2024-08-06 11:15:33
某代码因为外星人被外星人加入了大量WA0pts导致震惊WA0pts！某震惊因为蒟蒻被代码加入了大量外星人导致外星人蒟蒻！
by Fuziyu04 @ 2024-08-07 09:50:40
这题用位运算简简单单啊~众所周知a+b=(a^b)+((a&b)<<1),所以套一下就行了
by songyouyi @ 2024-08-11 14:53:01
btd?（小声逼逼）
by xingcode @ 2024-09-18 19:24:43
btd,qdwy