如果要把treap的优先级调整,要改哪里,每个函数都要改吗?(比如把最小优先改为最大优先)以下是对着模板打的
struct treap {
int l[100005],r[100005],v[100005],rnk[100005],s[100005],w[100005],sz,ans,rt;
void pushup(int x) {s[x]=s[l[x]]+s[r[x]]+w[x];}
void lrotate(int &k) {
int t=r[k];
r[k]=l[t],l[t]=k,s[t]=s[k],pushup(k),k=t;
}
void rrotate(int &k) {
int t=l[k];
l[k]=r[t],r[t]=k,s[t]=s[k],pushup(k),k=t;
}
void insert(int &k,int x) {//单点插入
if(!k) {
k=++sz,s[k]=1,w[k]=1,v[k]=x,rnk[k]=rand();
return;
}
s[k]++;
if(v[k]==x) w[k]++;
if(v[k]<x) {
insert(r[k],x);
if(rnk[r[k]]<rnk[k]) lrotate(k);
}
if(v[k]>x) {
insert(l[k],x);
if(rnk[l[k]]<rnk[k]) rrotate(k);
}
}
bool del(int &k,int x) {//单点删除
if(!k) return false;
if(v[k]==x) {
if(w[k]>1) {w[k]--,s[k]--;return true;}
if(l[k]==0||r[k]==0) {k=l[k]+r[k];return true;}
else if(rnk[l[k]]<rnk[r[k]]) {rrotate(k);return del(k,x);}
else {lrotate(k);return del(k,x);}
}
else if(v[k]<x) {
bool succ=del(r[k],x);
if(succ) s[k]--;return succ;
}
else {
bool succ=del(l[k],x);
if(succ) s[k]--;return succ;
}
}
int queryrank(int k,int x) {//单点查询排名
if(!k) return 0;
if(v[k]==x) return s[l[k]]+1;
else if(x>v[k]) return s[l[k]]+w[k]+queryrank(r[k],x);
else return queryrank(l[k],x);
}
int querynum(int k,int x) {//单点查询数值
if(!k) return 0;
if(x<=s[l[k]]) return querynum(l[k],x);
else if(x>s[l[k]]+w[k]) return querynum(r[k],x-s[l[k]]-w[k]);
else return v[k];
}
void queryp(int k,int x) {
if(!k) return;
if(v[k]<x) ans=k,queryp(r[k],x);
else queryp(l[k],x);
}
int querypre(int k,int x) {//单点查询前驱
ans=0;
queryp(k,x);
if(!ans) return -1;
else return v[ans];
}
void querys(int k,int x) {
if(!k) return;
if(v[k]>x) ans=k,querys(l[k],x);
else querys(r[k],x);
}
int querysub(int k,int x) {//单点查询后继
ans=0;
querys(k,x);
if(!ans) return -1;
else return v[ans];
}
}t;