【填坑】bzoj3224 splay裸题

时间:2022-08-31 23:14:26

人生第一道splay不出所料是一道裸题,一道水题,一道2k代码都不到的题

 #include <cstdio>
int root,N=,n,p,q;
int fa[],c[][],size[],sp[];
void rot(int x)
{
int y=fa[x],k=(c[y][]==x);
size[y]=size[c[y][k]]+size[c[x][k]]+;size[x]=size[c[x][!k]]+size[y]+;
c[y][!k]=c[x][k];fa[c[y][!k]]=y;
fa[x]=fa[y];if(fa[y])c[fa[y]][c[fa[y]][]==y]=x;
c[x][k]=y;fa[y]=x;
}
void rots(int x,int g)
{
for(int y=fa[x];y!=g;rot(x),y=fa[x])
if(fa[y]!=g) rot((x==c[y][])==(y==c[fa[y]][])?y:x);
if(g==) root=x;
}
void insert(int x)
{
int y=root;
while(c[y][x>sp[y]]) y=c[y][x>sp[y]];
sp[++N]=x;c[N][]=c[N][]=;fa[N]=y;if(y)c[y][x>sp[y]]=N;
rots(N,);
}
void del(int x)
{
int y=root;
while(sp[y]!=x) y=c[y][x>sp[y]];
rots(y,);y=c[root][];
bool b;
if(!y) b=,y=c[root][];else b=;
while(c[y][b]) y=c[y][b];
rots(y,root);
c[y][b]=c[root][b];fa[c[root][b]]=y;fa[y]=;root=y;
size[y]=size[c[y][!b]]+size[c[y][b]];
}
int rank(int x)
{
int y=root,ans=;
if(x==){
printf("");
}
while(y)
if(x>sp[y])
ans+=size[c[y][]]+,y=c[y][];
else y=c[y][];
return ans+;
}
int num(int x)
{
int y=root;
while(x)
if(size[c[y][]]+<x)
x-=size[c[y][]]+,y=c[y][];
else if(size[c[y][]]+==x) return sp[y];
else y=c[y][];
return sp[y];
}
int pre(int x)
{
int ans;
for(int y=root;y;)
if(sp[y]<x)
ans=sp[y],y=c[y][];
else y=c[y][];
return ans;
}
int nex(int x)
{
int ans;
for(int y=root;y;)
if(sp[y]<=x)
y=c[y][];
else ans=sp[y],y=c[y][];
return ans;
}
int main()
{
freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&p,&q);
if(p==) insert(q);
if(p==) del(q);
if(p==) printf("%d\n",rank(q));
if(p==) printf("%d\n",num(q));
if(p==) printf("%d\n",pre(q));
if(p==) printf("%d\n",nex(q));
}
return ;
}

貌似所有该犯的问题都犯了一遍了,,,感觉自己逻辑不够严谨啊

难道要背板???那么长感觉下不来啊

【填坑】bzoj3224 splay裸题的更多相关文章

  1. bzoj3223&colon; Tyvj 1729 文艺平衡树 splay裸题

    splay区间翻转即可 /************************************************************** Problem: 3223 User: walf ...

  2. 【模板篇】splay&lpar;填坑&rpar;&plus;模板题&lpar;普通平衡树&rpar;

    划着划着水一不小心NOIP还考的凑合了… 所以退役的打算要稍微搁置一下了… 要准备准备省选了…. 但是自己已经啥也不会了… 所以只能重新拾起来… 从splay开始吧… splay我以前扔了个板子来着, ...

  3. 动归专题QAQ(两天创造的刷题记录哟!✿✿ヽ&lpar;&&num;176&semi;&bigtriangledown;&&num;176&semi;&rpar;ノ✿✿)(未填坑)

    1092 采药:由于没有限制开始时间和结束时间,01背包就好了 1095 开心的金明:01背包,无fuck说 1104 摆花:f[i][j]表示摆了i种花,第i种花摆了j种的方案数,乱转移0.0(感觉 ...

  4. HDU 1711 Number Sequence&lpar;KMP裸题,板子题,有坑点&rpar;

    Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  5. 【填坑向】bzoj2038小Z的袜子 莫队

    学莫队必做题,,,但是懒得写.今天来填个坑 莫队水题 莫队实际上就是按一个玄学顺序来离线计算询问,保证复杂度只会多一个n1/2,感觉是玄学(离线算法都很玄学) 易错点:要开long long(卡我半天 ...

  6. 【填坑向】spoj COT&sol;bzoj2588 Count on a tree

    这题是学主席树的时候就想写的,,, 但是当时没写(懒) 现在来填坑 = =日常调半天lca(考虑以后背板) 主席树还是蛮好写的,但是代码出现重复,不太好,导致调试的时候心里没底(虽然事实证明主席树部分 ...

  7. LCT裸题泛做

    ①洞穴勘测 bzoj2049 题意:由若干个操作,每次加入/删除两点间的一条边,询问某两点是否连通.保证任意时刻图都是一个森林.(两点之间至多只有一条路径) 这就是个link+cut+find roo ...

  8. BZOJ 3680&colon; 吊打XXX【模拟退火算法裸题学习,爬山算法学习】

    3680: 吊打XXX Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special JudgeSubmit: 3192  Solved: 1198[Sub ...

  9. &num;YCB&num;待做题目与填坑资料

    各种填坑资料(qwq) 主席树(by YL)戳 树套树(by ZSY)戳 不要问我这些题咋来的(查大佬的水表呗) 题目列表: [HDU5977]Garden of Eden [BZOJ2752][HA ...

随机推荐

  1. 如何安全地关闭MySQL实例

    如何安全地关闭MySQL实例 转载自:http://imysql.com/2014/08/13/mysql-faq-howto-shutdown-mysqld-fulgraceful.shtml 本文 ...

  2. canvas对象arc函数的使用-遁地龙卷风

    (-1)写在前面 我用的是chrome49 <canvas id="lol" height="300"></canvas> (1)详细介 ...

  3. hdu 2059&lpar;dp&rpar;

    题意:容易理解... 思路:dp[i]表示乌龟到达第i个充电站时最少花费时间到第 i 个充电站后,从起点开始遍历到第 i-1 个充电站,得到最少花费时间 状态转移方程:dp[i]=min(dp[j]+ ...

  4. javascript&colon;Array&period;slice&period;call 到Array&period;prototype&period;slice&period;call

    举个从对象到数组的例子: var obj={}; obj[1]=1; obj[2]=2; obj.length=2; var arr =Array.prototype.slice.call(obj); ...

  5. iOS开发——NSArray中的字典排序

    手头上碰到一个项目,需要给数组中的字典中的一个字段排序,想了想,干脆再字典中增加一个字段,用来记录需要排序字段的第一个字符,用它来作为比较的对象,进行排序. - (void)viewDidLoad { ...

  6. win10 uwp Window&period;Current&period;Dispatcher中Current为null

    本文说的是进行网络中异步界面出现的错误,可能带有一定的主观性和局限性,说的东西可能不对或者不符合每个人的预期.如果觉得我有讲的不对的,就多多包含,或者直接关掉这篇文章,但是请勿生气或者发怒吐槽,可以在 ...

  7. MariaDB主从复制的逻辑与实现

    一.关系型数据库的劣势 “关系型数据库:指采用了关系模型来组织数据的数据库,而关系模型指的就是二维表格模型,而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织.”——Wiki 关系型数据 ...

  8. Windows Server 2016-WinSer 2016标准版与数据中心版的区别

    今天在整理文章的时候看到有读者问到他现在的测试环境是用的Windows Server 2016标准版,和我现阶段系列文章的环境是否有区别. 其实针对Windows Server 2016 Active ...

  9. NOI 2002 贪吃的九头龙

    树形dp #include<bits/stdc++.h> #define N 305 using namespace std; struct LEB{ int to,nxt,w; }e[N ...

  10. onsubmit解惑

    1.onsubmit的位置: onsubmit只存在于html <form>中,js的form中 2.submit与onsubmit的区别 发生顺序:onsubmit -> subm ...