https://www.luogu.org/PRoblem/show?pid=1486#sub 我以前的spaly他妈全抄模版的，然后觉得这样太颓废了，就很装逼地想自己写这题； 其实我理论都懂的，所以我就认为自己应该何以靠自己的力量去做出来； 然后做了两个晚上+1H的在校时间； 算算有6，7个小时呢； 真日了狗了 网上的模版反正烂大街的，这道题hzwer的spaly写的很烂的，结果过了（bz过了，洛谷死循环） 然后你随便翻开一个模版就看到什么zigzag压成一个函数啊，什么函数参数带&这个东西； 这样并不会给程序加速； 我也不觉得这样会方便； 我反正就是朴实的spaly；
这题的思路我不想讲了，我做了6,7个小时不是卡在思路上的； 关于思路你们就自己去找别的题解或者看代码把； 但是我要讲一下关于del的问题； 我们有一个x(代码中x指Min-sum)，现在我们要把所有权值小于x的节点全部删掉； std：我们找到x的后继，把他提到根节点，然后把左子树删光；很有道理对不对； 我们看一下正确的代码；
int del(int te){//返回删了几个 int k=0,num=-1,x=rt; while(x) if(sp[x].v<te)x=sp[x].r;else{ if(sp[x].v<k||!k){ k=sp[x].v; num=x; } x=sp[x].l; } if(num==-1){ k=sp[rt].s; rt=0;return k; } splay(num,sp[rt].fa); k=sp[sp[rt].l].s; sp[rt].s-=k; sp[rt].l=0; return k;}没什么毛病； 但是这是我一开始写的代码
int del(int te){ int k=0,num=rt,x=rt; while(x) if(sp[x].v<te)x=sp[x].r;else{ if(sp[x].v<k||!k){ k=sp[x].v; num=x; } x=sp[x].l; } if(!num){ k=sp[rt].s; rt=0;return k; } splay(num,sp[rt].fa); k=sp[sp[rt].l].s; sp[rt].s-=k; sp[rt].l=0; return k;}这个就WA了，因为我没有考虑关于全部删除的问题，所以num一开始要先赋值-1，最后特判； 这种细节是抄板子的人所不会考虑的； 然后我们再来看看我之前写的错误的del； 为什么错误，不明真相；
void del(int x){ while(sp[x].l*sp[x].r){ zag(x); sp[sp[x].fa].s-=sp[x].w; } if(x==rt)rt=sp[x].l+sp[x].r;else if(sp[sp[x].fa].v<sp[x].v)sp[sp[x].fa].r=sp[x].l+sp[x].r;else sp[sp[x].fa].l=sp[x].l+sp[x].r; sp[sp[x].l+sp[x].r].fa=sp[x].fa;}void dfs(int k){ if(!k)return; if(sp[k].v+sum<Min){ans+=sp[k].w;q[++tot]=k;dfs(sp[k].r);} dfs(sp[k].l);}if(cc=='S'){ sum-=x; dfs(rt); while(tot)del(q[tot--]); }这个是我一开始的写法，就是把不符合 的数一个一个找出来一个一个删掉；死循环； 我也不知道这个怎么错了； 估计就是父节点说明搞错，少了说明特判； 然后是改进版；
int dfs(int k){ if(!k)return 0; int ans=0; if(sp[k].v+sum<Min){ ans=sp[sp[k].l].s+sp[k].w; if(k==rt)rt=sp[k].r;else if(sp[sp[k].fa].v<sp[k].v)sp[sp[k].fa].r=sp[k].r; else sp[sp[k].fa].l=sp[k].r; if(sp[k].r)sp[sp[k].r].fa=sp[k].fa; ans+=dfs(sp[k].r); }else ans=dfs(sp[k].l); sp[k].s-=ans; return ans;}这个就是找到不对的点，直接把左子树全部删掉，把右子树接起来； 又踏马不知道哪里错了； 估计又是什么地方没特判； 那个人说splay好写的，你给我站出来！！ 然后如果您看出上面的俩个程序的问题所在，告诉我谢谢；
总结 1.链接节点的时候一定要考虑全面，而且要特判跟的情况； 2.各种情况都要特判； 3.不要直接抄别人的模版；
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;struct SP{ int l,r,v,s,w,fa;}sp[100005];int tot,q[100005];int n,m,x,y,z,sum,ans,nn,Min,rt,num;char cc;void up(int x){sp[x].s=sp[sp[x].l].s+sp[sp[x].r].s+sp[x].w;}void zig(int x){ int y=sp[x].r; if(x==rt)rt=y;else if(sp[sp[x].fa].v<sp[x].v)sp[sp[x].fa].r=y;else sp[sp[x].fa].l=y; sp[sp[y].l].fa=x; sp[x].r=sp[y].l; sp[y].l=x; sp[y].fa=sp[x].fa; sp[x].fa=y; sp[y].s=sp[x].s; up(x);}void zag(int x){ int y=sp[x].l; if(x==rt)rt=y;else if(sp[sp[x].fa].v<sp[x].v)sp[sp[x].fa].r=y;else sp[sp[x].fa].l=y; sp[sp[y].r].fa=x; sp[x].l=sp[y].r; sp[y].r=x; sp[y].fa=sp[x].fa; sp[x].fa=y; sp[y].s=sp[x].s; up(x);}void splay(int x,int k){ while(sp[x].fa!=k){ int y=sp[x].fa,z=sp[y].fa; if(z!=k) if((sp[y].v<sp[x].v)^(sp[z].v<sp[y].v)) if(sp[y].v<sp[x].v)zig(y);else zag(y); else if(sp[z].v<sp[y].v)zig(z);else zag(z); y=sp[x].fa; z=sp[y].fa; if(sp[y].v<sp[x].v)zig(y);else zag(y); }}void insert(int x){ if(!rt){rt=++nn;sp[rt].s=sp[rt].w=1;sp[rt].v=x;return;} int k=rt,kk; while(k){ kk=k; sp[k].s++; if(sp[k].v==x){sp[k].w++;return;} if(sp[k].v<x)k=sp[k].r;else k=sp[k].l; } sp[++nn].v=x; sp[nn].fa=kk; sp[nn].s=sp[nn].w=1; if(sp[kk].v<x)sp[kk].r=nn;else sp[kk].l=nn; splay(nn,sp[rt].fa);}int del(int te){ int k=0,num=-1,x=rt; while(x) if(sp[x].v<te)x=sp[x].r;else{ if(sp[x].v<k||!k){ k=sp[x].v; num=x; } x=sp[x].l; } if(num==-1){ k=sp[rt].s; rt=0;return k; } splay(num,sp[rt].fa); k=sp[sp[rt].l].s; sp[rt].s-=k; sp[rt].l=0; return k;}int find(int k,int x){ if(x>num-ans)return -1-sum; if(sp[sp[k].r].s+1<=x&&x<=sp[sp[k].r].s+sp[k].w)return sp[k].v; if(sp[sp[k].r].s>=x)return find(sp[k].r,x); return find(sp[k].l,x-sp[sp[k].r].s-sp[k].w);}int main(){ scanf("%d%d",&m,&Min); while(m--){ scanf("/n%c %d",&cc,&x); if(cc=='I'&&x<Min)continue;else if(cc=='I')insert(x-sum),num++;else if(cc=='A')sum+=x;else if(cc=='S'){ sum-=x; ans+=del(Min-sum); }else printf("%d/n",find(rt,x)+sum); } printf("%d",ans);}新闻热点
疑难解答
