学完模版后就开始在COGS上刷题了,但一直没有整理在一起,发此文记录一下（操作名称参见 treap 模版 http://blog.csdn.net/lcomyn/article/details/42582627）
COGS 62 HNOI 宠物收养所
题意很简单,大致就是求前驱和后继中较接近x值的点,所需操作insert（包括tlr,trr，下同）,delete,tpred,tsucc;需要记录一下宠物和主人的数量（这题第一眼我还以为要建两棵平衡树） code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val,fix,wgt,size;
treap_node(int val): val(val) {left=right=NULL; wgt=size=1; fix=rand();}
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *root;
int n;
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p)
p=new treap_node(value);
else
{
if (value==p->val)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
void del(treap_node *&p,int value)
{
if (p->val==value)
{
if (p->wgt==1)
{
if (!p->left||!p->right)
{
if (!p->left)
p=p->right;
else
p=p->left;
}
else
{
if (p->left->fix<p->right->fix)
{
trr(p);
del(p->right,value);
}
else
{
tlr(p);
del(p->left,value);
}
}
}
else
p->wgt--;
}
else
{
if (value<p->val)
del(p->left,value);
else
del(p->right,value);
}
if (p!=NULL) p->Maintain();
}
treap_node* tpred(treap_node *&p,int value,treap_node* best)
{
if (!p) return best;
if (p->val<=value)
return tpred(p->right,value,p);
else
return tpred(p->left,value,best);
}
treap_node* tsucc(treap_node *&p,int value,treap_node* best)
{
if (!p) return best;
if (p->val>=value)
return tsucc(p->left,value,p);
else
return tsucc(p->right,value,best);
}
int main()
{
int i,kind,a,n0,n1;
int sum,x,y,t;
freopen("pet.in","r",stdin);
freopen("pet.out","w",stdout);
treap_node *t1,*t2;
treap_node *null=NULL;
n0=0; n1=0; sum=0;
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d%d",&kind,&a);
if (kind==0)
{
t1=t2=null; x=y=2100000000;
if (n1!=0)
{
t1=tpred(root,a,null);
t2=tsucc(root,a,null);
if (t1)
x=a-t1->val;
if (t2)
y=t2->val-a;
t=min(x,y);
sum=(sum+t)%1000000;
if (x<=y)
del(root,t1->val);
else
del(root,t2->val);
n1--;
}
else
{
n0++;
insert(root,a);
}
}
if (kind==1)
{
t1=t2=null; x=y=2100000000;
if (n0!=0)
{
t1=tpred(root,a,null);
t2=tsucc(root,a,null);
if (t1)
x=a-t1->val;
if (t2)
y=t2->val-a;
t=min(x,y);
sum=(sum+t)%1000000;
if (x<=y)
del(root,t1->val);
else
del(root,t2->val);
n0--;
}
else
{
n1++;
insert(root,a);
}
}
}
printf("%d\n",sum%1000000);
fclose(stdin);
fclose(stdout);
}
COGS NOI 2004 郁闷的出纳员
题意很简单，但是个人觉得我的想法可能时间复杂度稍高（我用一个数组记录了修改值时低于平均工资的序号，然后一并删除），所需操作，insert,delete（已知序号）,kth,整体修改（chg） code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val,fix,wgt,size;
treap_node(int val): val(val) {left=right=NULL; size=wgt=1; fix=rand(); }
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *root,*delt[100001];
int n,minn,size,i;
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p)
p=new treap_node(value);
else
{
if (value==p->val)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
treap_node* kth(treap_node *&p,int k)
{
if (k<p->lsize()+1)
return kth(p->left,k);
else
if (k>p->lsize()+p->wgt)
return kth(p->right,k-p->lsize()-p->wgt);
else
return p;
}
void del(treap_node *&p,treap_node *&d)
{
if (p==d)
{
if (p->wgt==1)
{
if (!p->left||!p->right)
{
if (!p->left)
p=p->right;
else
p=p->left;
}
else
{
if (p->left->fix<p->right->fix)
{
trr(p);
del(p->right,d);
}
else
{
tlr(p);
del(p->left,d);
}
}
}
else
p->wgt--;
}
else
{
if (d->val<p->val)
del(p->left,d);
if (d->val>p->val)
del(p->right,d);
}
if (p!=NULL) p->Maintain();
}
void chg(treap_node *&p,int a)
{
int i;
p->val+=a;
if (p->val<minn)
{
for (i=1;i<=p->wgt;++i)
{
size++;
delt[size]=p;
}
}
if (p->left)
chg(p->left,a);
if (p->right)
chg(p->right,a);
if (p!=NULL)
p->Maintain();
}
int main()
{
int a,j,m,z;
char c;
freopen("cashier.in","r",stdin);
freopen("cashier.out","w",stdout);
treap_node *null=NULL;
scanf("%d%d",&n,&minn);
m=0; z=0;
for (i=1;i<=n;++i)
{
scanf("%*c%c%d",&c,&a);
if (c=='I'&&a>=minn)
{
m++;
insert(root,a);
}
if (c=='A'||c=='S')
{
size=0;
memset(delt,0,sizeof(delt));
if (c=='S')
a=-a;
chg(root,a);
m-=size; z+=size;
for (j=1;j<=size;++j)
del(root,delt[j]);
}
if (c=='F')
{
treap_node *t;
if (a>m)
printf("-1\n");
else
{
t=kth(root,m-a+1);
if (t)
printf("%d\n",t->val);
}
}
}
printf("%d\n",z);
fclose(stdin);
fclose(stdout);
}
COGS 516 求和
题目较难，需要搜索树上结点，不过仔细思考还是可以想得出来的，所需操作insert,搜索（search，当此结点值>=k时，继续搜索右子树，反之搜索左子树）code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val;
int fix,wgt,size;
treap_node(int val):val(val) {left=right=NULL; wgt=size=1; fix=rand(); }
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *root;
int n;
int P,k;
int a[100001];
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p)
p=new treap_node(value);
else
{
if (p->val==value)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
int search(treap_node *&p,int value,int best)
{
if (!p) return best;
if ((value-p->val+P)%P>=k)
return search(p->right,value,min(best,(value-p->val+P)%P));
else
return search(p->left,value,best);
}
int main()
{
int i,j,t,ans;
int x;
treap_node *null=NULL;
freopen("suma.in","r",stdin);
freopen("suma.out","w",stdout);
ans=2100000000;
scanf("%d%d%d",&n,&k,&P);
insert(root,0);
for (i=1;i<=n;++i)
{
x=0;
scanf("%lld",&x);
x=x%P;
a[i]=(a[i-1]+x)%P;
ans=min(ans,search(root,a[i],2100000000));
insert(root,a[i]);
}
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
}
COGS 1431 HNOI 永无乡
比较综合的题目，并查集+Treap+启发式合并，学会了合并操作，所需操作insert,merge,kth code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val,fix,wgt,size;
treap_node(int val): val(val) {left=right=NULL; wgt=size=1; fix=rand();}
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *root[100001];
int n,m,q,father[100001],a[100001],f[100001];
int find(int x)
{
if (x!=father[x])
father[x]=find(father[x]);
return father[x];
}
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p)
p=new treap_node(value);
else
{
if (p->val==value)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
void merge(treap_node *&a,treap_node *&b)
{
if (a->left) merge(a->left,b);
if (a->right) merge(a->right,b);
insert(b,a->val);
}
treap_node *kth(treap_node *&p,int k)
{
if (k<p->lsize()+1)
return kth(p->left,k);
else
if (k>p->lsize()+p->wgt)
return kth(p->right,k-p->lsize()-p->wgt);
else
return p;
}
int main()
{
int i,x,num,y,r1,r2;
char ch;
treap_node *null=NULL,*t;
freopen("bzoj_2733.in","r",stdin);
freopen("bzoj_2733.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i)
{
scanf("%d",&x);
a[i]=x;
father[i]=i;
f[x]=i;
insert(root[i],x);
}
for (i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
r1=find(x); r2=find(y);
if (r1!=r2)
{
if (root[r1]->size<=root[r2]->size)
{
father[r1]=r2;
merge(root[r1],root[r2]);
root[r1]==null;
}
else
{
father[r2]=r1;
merge(root[r2],root[r1]);
root[r2]=null;
}
}
}
scanf("%d",&q);
for (i=1;i<=q;++i)
{
while(true)
{
scanf("%c",&ch);
if (ch=='B'||ch=='Q') break;
}
scanf("%d%d",&x,&y);
r1=find(x);
if (ch=='Q')
{
if (y>root[r1]->size)
printf("-1\n");
else
{
t=kth(root[r1],y);
printf("%d\n",f[t->val]);
}
}
if (ch=='B')
{
r1=find(x); r2=find(y);
if (root[r1]->size<=root[r2]->size)
{
father[r1]=r2;
merge(root[r1],root[r2]);
root[r1]=null;
}
else
{
father[r2]=r1;
merge(root[r2],root[r1]);
root[r2]=null;
}
}
}
fclose(stdin);
fclose(stdout);
}
COGS 1533 营业额统计
模版题，所需操作insert,tpred,tsucc（严重吐槽此题需要自己补0） code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val,fix,wgt,size;
treap_node(int val):val(val) {left=right=NULL; wgt=size=1; fix=rand(); }
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *root;
int n;
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p)
p=new treap_node(value);
else
{
if (value==p->val)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
treap_node* tpred(treap_node *&p,int value,treap_node *&best)
{
if (!p) return best;
if (p->val<=value)
return tpred(p->right,value,p);
else
return tpred(p->left,value,best);
}
treap_node* tsucc(treap_node *&p,int value,treap_node *&best)
{
if (!p) return best;
if (p->val>=value)
return tsucc(p->left,value,p);
else
return tsucc(p->right,value,best);
}
int main()
{
int i,ans,sum,x;
freopen("turnover.in","r",stdin);
freopen("turnover.out","w",stdout);
sum=0;
treap_node *temp;
treap_node *null=NULL;
scanf("%d",&n);
for (i=1;i<=n;++i)
{
if(scanf("%d",&x)==EOF)
x=0;
ans=2100000000;
temp=tpred(root,x,null);
if (temp)
ans=min(ans,x-temp->val);
temp=tsucc(root,x,null);
if (temp)
ans=min(ans,temp->val-x);
if (i==1) ans=x;
sum+=ans;
insert(root,x);
}
printf("%d\n",sum);
fclose(stdin);
fclose(stdout);
}
BZOJ 1058 报表统计
一道不简单的平衡树（神犇请无视），对于MIN_SORT_GAP我们可以建立一棵平衡树，每插入一个节点，就查询一个数的前驱、后继，取最小值与之前的最小值取min。
对于MIN_GAP，由于插入一个节点，破坏了一对差值关系，新建了两对差值关系，放在小根堆中，取堆根中元素即可。code：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct treap_node{
treap_node *left,*right;
int val,wgt,size,fix;
treap_node(int val): val(val) {left=right=NULL; wgt=size=1; fix=rand();}
int lsize()
{
if (left)
return left->size;
else
return 0;
}
int rsize()
{
if (right)
return right->size;
else
return 0;
}
void Maintain()
{
size=wgt;
size+=lsize()+rsize();
}
};
treap_node *roota;
int a[500001]={0},en[500001]={0},n,m,v[1500001]={0},heap[1500001]={0},pos[1500001]={0},f[500001]={0},tot;
void tlr(treap_node *&a)
{
treap_node *b=a->right;
a->right=b->left;
b->left=a;
a->Maintain();
b->Maintain();
a=b;
}
void trr(treap_node *&a)
{
treap_node *b=a->left;
a->left=b->right;
b->right=a;
a->Maintain();
b->Maintain();
a=b;
}
void insert(treap_node *&p,int value)
{
if (!p) p=new treap_node(value);
else
{
if (value==p->val)
p->wgt++;
if (value<p->val)
{
insert(p->left,value);
if (p->left->fix<p->fix)
trr(p);
}
if (value>p->val)
{
insert(p->right,value);
if (p->right->fix<p->fix)
tlr(p);
}
}
p->Maintain();
}
treap_node *tpred(treap_node *&p,int value,treap_node *best)
{
if (!p) return best;
else
if (p->val<=value)
return tpred(p->right,value,p);
else
return tpred(p->left,value,best);
}
treap_node *tsucc(treap_node *&p,int value,treap_node *best)
{
if (!p) return best;
else
if (p->val>=value)
return tsucc(p->left,value,p);
else
return tsucc(p->right,value,best);
}
void up(int x)
{
int i;
while (x>1)
{
i=x/2;
if (v[heap[x]]<v[heap[i]])
{
swap(pos[heap[x]],pos[heap[i]]);
swap(heap[x],heap[i]);
}
x=i;
}
}
void down(int x)
{
int i;
while (x*2<=tot)
{
if (x*2==tot||(x*2<tot&&v[heap[x*2]]<v[heap[x*2+1]])) i=x*2;
else i=x*2+1;
if (v[heap[x]]>v[heap[i]])
{
swap(pos[heap[x]],pos[heap[i]]);
swap(heap[x],heap[i]);
}
x=i;
}
}
int main()
{
treap_node *null=NULL,*t;
char s[50];
int i,j,x,minn=2100000000,num,mint;
tot=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i)
{
scanf("%d",&a[i]);
en[i]=a[i];
if (i>1)
{++tot; v[tot]=abs(a[i]-a[i-1]);pos[tot]=tot; heap[tot]=tot; f[i-1]=tot; up(tot);}
t=tpred(roota,a[i],null);
if (t!=NULL)
minn=min(minn,a[i]-t->val);
t=tsucc(roota,a[i],null);
if (t!=NULL)
minn=min(minn,t->val-a[i]);
insert(roota,a[i]);
}
mint=v[heap[1]];
for (i=1;i<=m;++i)
{
scanf("%s",&s);
if (s[0]=='I')
{
scanf("%d%d",&num,&x);
if (num<n)
{
v[f[num]]=2100000000; down(pos[f[num]]);
++tot; v[tot]=abs(x-en[num]); pos[tot]=tot; heap[tot]=tot; up(tot);
++tot; v[tot]=abs(a[num+1]-x); pos[tot]=tot; heap[tot]=tot; f[num]=tot; up(tot);
}
else
{ ++tot; v[tot]=abs(x-en[num]); pos[tot]=tot; heap[tot]=tot; up(tot);}
en[num]=x; mint=v[heap[1]];
t=tpred(roota,x,null);
if (t!=NULL)
minn=min(minn,x-t->val);
t=tsucc(roota,x,null);
if (t!=NULL)
minn=min(minn,t->val-x);
insert(roota,x);
}
if (s[0]=='M')
{
if (s[4]=='S')
printf("%d\n",minn);
if (s[4]=='G')
printf("%d\n",mint);
}
}
}