thousands_of_years @ 2024-07-13 09:05:08
我自己先敲了一个平衡树，hack T 了；
下载了hack 数据，拿平衡树题解测试；
最后冒死去洛谷测试，还是T了；不要棕我
例如：@Masky 大佬，对不住了
by thousands_of_years @ 2024-07-13 09:08:29
@wosile
by ycyxh1 @ 2024-07-13 09:14:02
@The_last_one
fhq-treap不会T
#include<bits/stdc++.h>
using namespace std;
struct Node{
int l,r,key,val,len;
}a[10000001];
int tot=0,rot;
void push_up(int p){
a[p].len=a[a[p].l].len+a[a[p].r].len+1;
}
//-----------------------------------------合并
int merge(int rot1,int rot2){
if(rot1==0){
return rot2;
}
else if(rot2==0){
return rot1;
}
if(a[rot1].key<a[rot2].key){
a[rot1].r=merge(a[rot1].r,rot2);
push_up(rot1);
return rot1;
}
else{
a[rot2].l=merge(rot1,a[rot2].l);
push_up(rot2);
return rot2;
}
}
//-----------------------------------------按权值拆
void val_split(int now,int k,int &rot1,int &rot2){
if(now==0){
rot1=0;
rot2=0;
return;
}
else if(a[now].val<=k){
rot1=now;
val_split(a[rot1].r,k,a[rot1].r,rot2);
}
else{
rot2=now;
val_split(a[rot2].l,k,rot1,a[rot2].l);
}
push_up(now);
}
//-----------------------------------------按排名拆
void k_split(int now,int k,int &rot1,int &rot2){
if(now==0){
rot1=0;
rot2=0;
return;
}
push_up(now);
if(a[a[now].l].len<k){
rot1=now;
k_split(a[rot1].r,k-a[a[rot1].l].len-1,a[rot1].r,rot2);
}
else{
rot2=now;
k_split(a[rot2].l,k,rot1,a[rot2].l);
}
push_up(now);
}
//-------------------------------------新建节点
void New_Node(int val){
a[++tot].key=rand()%114514+1;
a[tot].l=0;
a[tot].r=0;
int rot1,rot2,now=tot;
a[tot].len=1;
a[tot].val=val;
val_split(rot,val,rot1,rot2);
rot=merge(merge(rot1,now),rot2);
}
//-------------------------------------删除
void Erase(int val){
int rot1,rot2,rot3,rot4;
val_split(rot,val-1,rot1,rot2);
k_split(rot2,1,rot3,rot4);
rot=merge(rot1,rot4);
}
//-------------------------------------查找
int Find_k(int val){
int rot1,rot2;
val_split(rot,val-1,rot1,rot2);
int x=a[rot1].len+1;
rot=merge(rot1,rot2);
return x;
}
int Find_val(int k){
int rot1,rot2,rot3,rot4;
k_split(rot,k-1,rot1,rot2);
k_split(rot2,1,rot3,rot4);
int x=a[rot3].val;
rot=merge(rot1,merge(rot3,rot4));
return x;
}
int Find_last(int val){
int rot1,rot2,rot3,rot4;
val_split(rot,val-1,rot1,rot2);
k_split(rot1,a[rot1].len-1,rot3,rot4);
int x=a[rot4].val;
rot=merge(merge(rot3,rot4),rot2);
return x;
}
int Find_next(int val){
int rot1,rot2,rot3,rot4;
val_split(rot,val,rot1,rot2);
k_split(rot2,1,rot3,rot4);
int x=a[rot3].val;
rot=merge(rot1,merge(rot3,rot4));
return x;
}
//------------------------------------主函数
int main(){
srand(time(NULL));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
New_Node(x);
if(i%2==1){
printf("%d\n",Find_val(i/2+1));
}
}
return 0;
}by thousands_of_years @ 2024-07-13 09:17:14
额，但 @Masky 的题解通过不了；
先把他的撤了【坏笑】
by thousands_of_years @ 2024-07-13 10:46:47
还有那些题解志愿员啊？
by thousands_of_years @ 2024-07-13 10:57:54
@bykem
by thousands_of_years @ 2024-07-13 10:59:31
@lihanwen12
by anke2017 @ 2024-07-16 18:25:38
平衡树应该不会T吧
1e5随便写个常数正常的都能过吧
验证码wddd祭
by anke2017 @ 2024-07-16 18:27:38
比如这个（有快读快写单点50ms以内）
#include<bits/stdc++.h>
using namespace std;
inline char nc()
{
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int uread()
{
static char a;
a=nc();
while(!isdigit(a)){a=nc();}
int n=0;
while(isdigit(a))
{
n=(n<<1)+(n<<3);
n+=(a^48);
a=nc();
}
return n;
}
inline void uout(int x)
{
if(x==0) {putc('0',stdout);return;}
int ans=1;
int n[10]={0};
while(x)
{
n[ans]=x%10;
x/=10;
ans++;
}
for(int i=ans-1;i>=1;i--)
{
putc((char)(n[i]+48),stdout);
}
}
namespace _trie
{
const int _01trie_maxn=1e5+10;
const int _01trie_maxlog=30;
const int _01trie_root=1;
struct _01trie//?????????
{
int siz[_01trie_maxn*_01trie_maxlog];
int son[_01trie_maxn*_01trie_maxlog][2];
int now=_01trie_root;
int newnode()
{
now++;
son[now][0]=son[now][1]=0;
return now;
}
void init()
{
son[_01trie_root][0]=son[_01trie_root][1]=0;
now=_01trie_root;
}
void insert(int x)
{
int u=_01trie_root;
for(int i=_01trie_maxlog-1;i>=0;i--)
{
int v=(x>>i)&1;
if(!son[u][v])son[u][v]=newnode();
u=son[u][v];
siz[u]++;
}
}
int kth(int x)
{
int u=_01trie_root,now=0;
for(int i=_01trie_maxlog-1;i>=0;i--)
{
//printf("now=%d,u=%d,x=%d\n",now,u,x);
if(siz[son[u][0]]>=x)u=son[u][0];
else
{
x-=siz[son[u][0]];
now|=(1<<i);
u=son[u][1];
}
}
return now;
}
int rank(int x)
{
int ans=0;
int u=_01trie_root;
for(int i=_01trie_maxlog-1;i>=0;i--)
{
if((x>>i)&1)
{
ans+=siz[son[u][0]];
u=son[u][1];
}
else u=son[u][0];
if(!u)return ans+1;
}
return ans+1;
}
int pre(int x)
{
return kth(rank(x)-1);
}
int nxt(int x)
{
return kth(rank(x+1));
}
void print(int now)
{
if(!now)return;
printf("now=%d,lson=%d,rson=%d,size=%d\n",now,son[now][0],son[now][1],siz[now]);
print(son[now][0]);
print(son[now][1]);
}
};//struct
}//namespace
using namespace _trie;
//int n[100001];
_01trie trie;
int main()
{
trie.init();
//_01trie trie;
int a=uread();
for(int i=1,tmp;i<=a;i++)
{
trie.insert(uread());
if(i%2)
{
uout(trie.kth(i/2+1));putc('\n',stdout);
}
}
return 0;
}原谅我支持的是模版平衡树的功能，代码长些