一道平衡树的题目

1、道平衡树的题目题目描述要你维护一个集合，集合里面的元素为二元组（x,y）。这个集合中一开始有n个元素。支持如下操作：Insert,x0,y0,插入一个元素（xO,yO）。Delete,xO,删除所有x值为xO的元素。Querymin1,查询所有元素中x值最小的元素。Querymin2,查询所有元素中y值最小的元素。Query1,xO,查询集合中是否有x值为xO的元素。Query2,xO,查询集合中x值大于等于xO的第一个元素（不存在的话输出-1）。Query3,x0,查询x值小于等于xO的所有元素中y值的最小值（不存在的话输出-1）。Query4,k,查询集合中x值第k大的元素。Query5,

2、k,查询x值从小到大前k个元素的y值的最大值。1O.Query6,k,查询x值从小到大前k个元素的y值的和。保证输入的X中没有重复。数据范围：n=1e5，操作个数Q=1e5。输入格式第一行输入两个数n,Q,后面n行每行输入两个整数x,y。后面Q行每行进行一个操作。输出格式输出操作3-1O中的查询结果。这道题教会了我如果用平衡树来维护一些简单的辅助信息，极值、区间和等等（这道题我调了几乎一整天）。代码如下#include#include#include#include#include#include#include#include#include#include#include#include#

3、defineLLlonglong#definePIIpair#defineLtru.l#defineRtru.rusingnamespacestd;constintN=2e5+5,INF=1e9;structNodeintl,r;intx,y,val;为key,y为辅助信息intsize,max,min=1e9;maxnin记录y的最大值、最小值LLsum;记录以该节点为根的子树中的和trN;ntroot,idx;voidpushup(intu)由左右儿子节点推出父亲节点的信息tru.size=trL.size+trR.size+1;tru.sum=trL.sum+trR.sum+tru.y;

4、tru.max=max(tru.y,max(trL.max,trR.max);tru.min=min(tru.y,min(trL.min,trR.min);intgetNode(intkey,inty)创建新节点tr+idx.x=key;tridx.y=y;tridx.max=tridx.min=tridx.sum=y;tridx.size=1;tridx.val=rand();returnidx;voidzig(int&u)右旋intq=L;L=trq.r,trq.r=u;u=q;pushup(R);pushup(u);voidzag(int&u)左旋intq=R;R=trq.l,trq.l

5、=u;u=q;pushup(L);pushup(u);voidinsert(int&u,intkey,inty)插入一个节点(操作)if(!u)u=getNode(key,y);elseif(keytru.val)zig(u);elseinsert(R,key,y);if(trR.valtru.val)zag(u);pushup(u);voidremove(int&u,intkey)删除一个节点(操作)if(!u)return;if(tru.x=key)if(L|R)if(!R|trL.va卜trR.val)zig(u);remove(R,key);elsezag(u);remove(L,ke

6、y);elseu=0;elseif(keykey)returnget(L,key);returnget(R,key);intfind(int&u,intrank)找出树中排名为ank的节点(操作和操作)if(!u)return-1;if(trL.size=rank)returnfind(L,rank);if(trL.size+1=rank)returntru.x;returnfind(R,rank-trL.size-1);intgetPrev(intu,intkey)找出平衡树中小于等于ey的最大值(操作7if(!u)return-1;if(keytru.x)returngetNext(R,k

7、ey);returnmin(tru.x,getNext(L,key);intfindMax(int&u,intrank)找出树中x排名为1-rank的y的最大值(操作)if(!u)return-INF;if(trL.size=rank)returnfindMax(L,rank);if(trL.size+1=rank)returnmax(trL.max,tru.y);returnmax(trL.max,max(tru.y,findMax(R,rank-1-trL.size);intgetMin(int&u,intkey)找出树中x小于等于key的所有数的最小值(操作)if(!u)returnIN

8、F;if(key=rank)returnfindSum(L,rank);if(trL.size+1=rank)returntrL.sum+tru.y;returntrL.sum+tru.y+findSum(R,rank-1-trL.size);intmain()intn,m;scanf(%d%d,&n,&m);for(inti=1;i=INF)t=-1;printf(%dn,t);elseif(op=7)小于等于x的数中y的最小值scanf(%d,&x);intkey=getPrev(root,x);printf(%dn,getMin(root,key);elseif(op=8)的第k大元素scanf(%d,&x);printf(%dn,find(root,n-x