2333?
先记一下吧，这题现在全部都是照着题解做的，因为怎么改都改不出来，只好对着题解改，以后还要再做过
以后再也不用指针了！太恶心了！空指针可不止直接特判那么简单啊，竟然还要因为空指针写奇怪的分类讨论！
没错，就是那个诡异的55和63行。由于要返回删除x后x所在树的新根，要分类讨论：如果x是根且其两个子节点合并后为空，那么去掉x后新树树根为空；如果x是根且其两个子节点合并后不为空，那么去掉x后新树树根为两个子节点合并后的；如果x不是根，那么去掉x后新树树根为原来的find(x)。
另外，打了注释号的（不管是空注释还是被注释掉的语句）都表示此处出过错
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
multiset<int> sx;
void erase(int x)
{
//if(sx.find(x)!=sx.end())
sx.erase(sx.find(x));
}
struct Node
{
int data;int addv;
Node *ch[],*fa;
void pd()
{
if(addv)
{
if(ch[]) ch[]->addv+=addv,ch[]->data+=addv;
if(ch[]) ch[]->addv+=addv,ch[]->data+=addv;
addv=;//
}
}
}nodes[];
Node* find(Node* x)//
{
if(x==NULL) return x;//
while(x->fa) x=x->fa;
return x;
}
Node* merge(Node* a,Node* b)
{
if(!a) return b;
if(!b) return a;
//a->pd();b->pd();
if(a->data < b->data) swap(a,b);
a->pd();
a->ch[]=merge(a->ch[],b);
if(a->ch[])/**/ a->ch[]->fa=a;
swap(a->ch[],a->ch[]);
return a;
}
Node *q[];int q_num;
void solvetag(Node *x)//
{
while(x)q[++q_num]=x,x=x->fa;
//while(x->fa)q[++q_num]=x,x=x->fa;
while(q_num)q[q_num--]->pd();
}
Node* del(Node *x)//删除x，将x较大的儿子提上来，并返回它所在集合的新根节点
{
//if(x==NULL) return x;//''
solvetag(x);
Node *t=merge(x->ch[],x->ch[]),*f=x->fa,*rt;
rt=find(x);if(rt==x) rt=NULL;//
x->ch[]=x->ch[]=x->fa=NULL;
if(f)//
{
if(x==f->ch[]) f->ch[]=t;
else f->ch[]=t;
}
if(t)/**/ t->fa=f;
if(t) rt=find(t);//
return rt;
}
void add(Node *x,int val)
{
//if(x==NULL) return;
solvetag(x);
erase(find(x)->data);
//find(x)->data+=val;
x->data+=val;Node *t=del(x);
sx.insert(merge(x,t)->data);//puts("t1");
}
void hadd(Node *x,int val)
{
//if(x==NULL) return;//'
Node *p=find(x);
erase(p->data);
p->addv+=val;p->data+=val;
sx.insert(p->data);
}
int n,m,addx,Q;
char tmp[];
int main()
{
int i,t,x,y,v;Node *fx,*fy;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&t);
nodes[i].data=t;
//nodes[i].upd();
sx.insert(t);
}
scanf("%d",&Q);
//int axx=0;
while(Q--)
{
scanf("%s",tmp);
if(tmp[]=='U')
{
scanf("%d%d",&x,&y);
fx=find(nodes+x);fy=find(nodes+y);
if(fx==fy) continue;
//solvetag(nodes+x);solvetag(nodes+y);
if(merge(fx,fy)==fx) erase(fy->data);
else erase(fx->data);
}
else if(tmp[]=='A')
{
if(tmp[]=='')
{
scanf("%d%d",&x,&v);
add(nodes+x,v); }
else if(tmp[]=='')
{
scanf("%d%d",&x,&v);
hadd(nodes+x,v);
}
else if(tmp[]=='')
{
scanf("%d",&v);
addx+=v;
}
}
else if(tmp[]=='F')
{
//axx++;
//if(axx==54) printf(" %c ",tmp[1]);
if(tmp[]=='')
{
scanf("%d",&x);
solvetag(nodes+x);
printf("%d\n",nodes[x].data+addx);
}
else if(tmp[]=='')
{
scanf("%d",&x);
//solvetag(nodes+x);
printf("%d\n",find(nodes+x)->data+addx);
}
else if(tmp[]=='')
{
printf("%d\n",*(--sx.end())+addx);
} }
}
return ;
}
另外：本来是想不到去写斜堆的，因为斜堆并不保证任何意义上的平衡，如果用这个在节点上维护附加信息，那么标记传递还有找根什么的复杂度应该是假的。然而实际应用发现...并没有问题？仍然不会分析
另外：把堆合并改成非旋treap里面的样子，也可以过，而且用时几乎完全一样（只差几ms）（然而去掉swap两个子节点就不能了，或者将非旋treap合并里面一些对正确性无关紧要的东西乱改一下也不行，这次跟洛谷上某道可并堆模版不一样了...），说明非旋treap里面堆合并跟一般斜堆合并写法本质应该没有区别（只是保证中序遍历不变）。然而并不会分析？
另外：虽然不交换是错的，但是随机怎么摆却是对的！实际效果是只比斜堆慢了一点点。而且，即使斜堆真的会被卡随机堆也不可能被卡...应该吧
就比如这样
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
multiset<int> sx;
inline int rd()
{
static int x=;
return x=(48271LL*x+)%;
}
void erase(int x)
{
//if(sx.find(x)!=sx.end())
sx.erase(sx.find(x));
}
struct Node
{
int data;int addv;
Node *ch[],*fa;
void pd()
{
if(addv)
{
if(ch[]) ch[]->addv+=addv,ch[]->data+=addv;
if(ch[]) ch[]->addv+=addv,ch[]->data+=addv;
addv=;//
}
}
}nodes[];
Node* find(Node* x)//
{
if(x==NULL) return x;//
while(x->fa) x=x->fa;
return x;
}
Node* merge(Node* a,Node* b)
{
if(!a) return b;
if(!b) return a;
//a->pd();b->pd();
if(a->data < b->data) swap(a,b);
a->pd();
if(rd()%)
{
a->ch[]=merge(a->ch[],b);
if(a->ch[]) a->ch[]->fa=a;
}
else
{
a->ch[]=merge(a->ch[],b);
if(a->ch[]) a->ch[]->fa=a;
}
return a; }
Node *q[];int q_num;
void solvetag(Node *x)//
{
while(x)q[++q_num]=x,x=x->fa;
//while(x->fa)q[++q_num]=x,x=x->fa;
while(q_num)q[q_num--]->pd();
}
Node* del(Node *x)//删除x，将x较大的儿子提上来，并返回它所在集合的新根节点
{
//if(x==NULL) return x;//''
solvetag(x);
Node *t=merge(x->ch[],x->ch[]),*f=x->fa,*rt;
rt=find(x);if(rt==x) rt=NULL;//
x->ch[]=x->ch[]=x->fa=NULL;
if(f)//
{
if(x==f->ch[]) f->ch[]=t;
else f->ch[]=t;
}
if(t)/**/ t->fa=f;
if(t) rt=find(t);//
return rt;
}
void add(Node *x,int val)
{
//if(x==NULL) return;
solvetag(x);
erase(find(x)->data);
//find(x)->data+=val;
x->data+=val;Node *t=del(x);
sx.insert(merge(x,t)->data);//puts("t1");
}
void hadd(Node *x,int val)
{
//if(x==NULL) return;//'
Node *p=find(x);
erase(p->data);
p->addv+=val;p->data+=val;
sx.insert(p->data);
}
int n,m,addx,Q;
char tmp[];
int main()
{
int i,t,x,y,v;Node *fx,*fy;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&t);
nodes[i].data=t;
//nodes[i].upd();
sx.insert(t);
}
scanf("%d",&Q);
//int axx=0;
while(Q--)
{
scanf("%s",tmp);
if(tmp[]=='U')
{
scanf("%d%d",&x,&y);
fx=find(nodes+x);fy=find(nodes+y);
if(fx==fy) continue;
//solvetag(nodes+x);solvetag(nodes+y);
if(merge(fx,fy)==fx) erase(fy->data);
else erase(fx->data);
}
else if(tmp[]=='A')
{
if(tmp[]=='')
{
scanf("%d%d",&x,&v);
add(nodes+x,v); }
else if(tmp[]=='')
{
scanf("%d%d",&x,&v);
hadd(nodes+x,v);
}
else if(tmp[]=='')
{
scanf("%d",&v);
addx+=v;
}
}
else if(tmp[]=='F')
{
//axx++;
//if(axx==54) printf(" %c ",tmp[1]);
if(tmp[]=='')
{
scanf("%d",&x);
solvetag(nodes+x);
printf("%d\n",nodes[x].data+addx);
}
else if(tmp[]=='')
{
scanf("%d",&x);
//solvetag(nodes+x);
printf("%d\n",find(nodes+x)->data+addx);
}
else if(tmp[]=='')
{
printf("%d\n",*(--sx.end())+addx);
} }
}
return ;
}
我差点忘了一件事，就是相同权值的在堆里顺序无所谓，merge两个参数先后也是无所谓的。