Problem surface
Title Description
You need to write a data structure to maintain some numbers, which needs to provide the following operations:
- insert x \text{x} x number
- delete x \text{x} Number of x (if there are multiple identical numbers, only one will be deleted)
- query x \text{x} Ranking of x number (ranking is defined as the number of numbers smaller than the current number) +1 \text{+1} +1 )
- Query ranking is x \text{x} Number of x
- seek x \text{x} Precursor of x (defined as less than x \text{x} x. And the maximum number)
- seek x \text{x} Successor of x (successor defined as greater than) x \text{x} x. And the smallest number)
Input format
First behavior n \text{n} n. Indicates the number of operations, as shown below n \text{n} n lines, each line has two numbers opt \text{opt} opt and x x x， opt \text{opt} opt indicates the sequence number of the operation ( 1 ≤ opt ≤ 6 ) ( 1 \leq \text{opt} \leq 6) (1≤opt≤6)
Output format
For operation 3,4,5,6 \text{3,4,5,6} 3, 4, 5 and 6 output a number for each line, indicating the corresponding answer
Sample data
input
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
output
106465 84185 492737
Data range
about 100 % \text{100}\% 100% data, 1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1≤n≤105， ∣ x ∣ ≤ 1 0 7 |x| \le 10^7 ∣x∣≤107
Algorithm analysis
concept
Treap
Tree pile
\text {tree heap}
Tree heap, also known as tree heap in data structure
Treap
\text{Treap}
A heap is a random additional field that satisfies the nature of the heap
Binary search tree
[
1
]
\text {binary search tree} ^ {[1]}
Binary search tree [1], whose structure is equivalent to a binary search tree inserted with random data. The expected time complexity of its basic operation is
O
(
log
2
n
)
O(\log_{2}{n})
O(log2n). Compared with other balanced binary search trees,
Treap
\text{Treap}
The characteristics of Treap are
Simple implementation
\text{easy implementation}
The implementation is simple and can basically
Achieve random balance
\text {achieve random balance}
Structure to achieve random balance.
Treap
\text{Treap}
A tree is a tree
Binary sort tree
[
1
]
\text {binary sort tree} ^ {[1]}
Binary sort tree [1], its left subtree and right subtree are one respectively
Treap
\text{Treap}
Different from the general binary sort tree,
Treap
\text{Treap}
Treap records an additional data, which is
priority
\text {priority}
Priority.
Treap
\text{Treap}
While forming a binary sort tree with key codes, Treap also meets
heap
\text {heap}
The nature of the heap (here we assume that the priority of a node is greater than that of its children).
Binary search tree / binary sort tree
two
fork
search
Rope
tree
/
two
fork
Row
order
tree
[
1
]
{binary search tree / binary sort tree} ^ {[1]}
Binary search tree / binary sort tree [1]
two
fork
check
look for
tree
Binary lookup tree
Binary lookup tree(
B
i
n
a
r
y
S
e
a
r
c
h
T
r
e
e
Binary Search Tree
BinarySearchTree
two
fork
search
Rope
tree
Binary search tree
Binary search tree,
two
fork
Row
order
tree
Binary sort tree
Binary sort tree)
It is either an empty tree or a binary tree with the following properties:
- If its left subtree is not empty, the values of all nodes on the left subtree are less than the values of its root node;
- If its right subtree is not empty, the value of all nodes on the right subtree is greater than that of its root node;
- Its left and right subtrees are also binary sort trees.
application
Operation 1
To solve this problem, we can first process and model the data:
For example, this set of data
12 5 18 2 9 15 19 17 16
You can create a tree as shown in the figure
To do this, we only need to use the nature of binary search tree (mentioned above)
Recursively find the position where the node should be
#include<bits/stdc++.h>
#define INF 0x3fffffff
using namespace std;
int K,N,M,op,q,root,last,ans=0;
struct Node{//Define node
int val,l,r,cnt,size,f;
//val is the value, l and r are the left and right sons, and cnt is the number of current values,
//size is the number of current nodes and words, and f is a random number
}node[10000039];
void pushup(int p){
node[p].size=node[node[p].l].size+node[node[p].r].size+node[p].cnt;
//The number of all nodes is the number of nodes of the left son plus the number of nodes of the right son plus the number of current nodes
}
int newnode(int x){//New node (k is the number of nodes)
node[++K].val=x,node[K].cnt=node[K].size=1;//The value is x, cnt is 1, and the total number of subtrees and current nodes is 1
node[K].f=rand();//f is a random number
return K;
}
void insert(int &p,int x){//Insert operation (operation 1)
if(!p)p=newnode(x);//Create a new node when you find an empty location
else if(x==node[p].val){node[p].cnt++,node[p].size++;}
//If this node already exists, use cnt + + and size at the same time++
else if(x<node[p].val){insert(node[p].l,x);if(node[node[p].l].f<node[p].f)zag(p);}
//If x is smaller than the current value, go to the left
else if(x>node[p].val){insert(node[p].r,x);if(node[node[p].r].f<node[p].f)zig(p);}
//If x is greater than the current value, go to the right
pushup(p);
}
0
x
3
f
f
f
f
f
f
f
=
1073741823
0x3fffffff=1073741823
0x3fffffff=1073741823
0
x
f
f
f
f
f
f
f
f
=
4294967295
=
?
0xffffffff=4294967295=?
0xffffffff=4294967295=?
What are these two sentences for
Operation 2
zag and zig are right-handed and left-handed
void zag(int &p){
int k=node[p].l;
node[p].l=node[k].r,node[k].r=p,p=k;
pushup(node[p].r),pushup(p);
}
void zig(int &p){
int k=node[p].r;
node[p].r=node[k].l,node[k].l=p,p=k;
pushup(node[p].l),pushup(p);
}
void erase(int &p,int x){
if(node[p].val==x){//If the current point is the same as x
if(node[p].cnt>1)node[p].cnt--;//If the number is greater than 1, cnt will be used directly--
else if(!node[p].l)p=node[p].r;//If there is no left son, go right
else if(!node[p].r)p=node[p].l;//If there is no right son, turn left
//If you have them all, it depends on whose f is small and which way to turn
else if(node[node[p].l].f<node[node[p].r].f)zag(p),erase(node[p].r,x);
else if(node[node[p].l].f>node[node[p].r].f)zig(p),erase(node[p].l,x);
}
else if(node[p].val>x)erase(node[p].l,x);
else if(node[p].val<x)erase(node[p].r,x);
//Also left or right
pushup(p);
}
Operation 3 and 4
int getrank(int p,int x){
if(!p)return 0;
else if(node[p].val>x)return getrank(node[p].l,x);
else if(node[p].val<x)return getrank(node[p].r,x)+node[node[p].l].size+node[p].cnt;
else if(node[p].val==x)return node[node[p].l].size+1;
}
int getval(int p,int x){
if(x<=node[node[p].l].size+node[p].cnt&&x>node[node[p].l].size)return node[p].val;
else if(x<=node[node[p].l].size)return getval(node[p].l,x);
else return getval(node[p].r,x-node[node[p].l].size-node[p].cnt);
}//Understand for yourself
Operation 5 and 6
int get_pre(int p,int x){
if(!p)return -INF;
else if(x>node[p].val)return comp(node[p].val,get_pre(node[p].r,x),1);
else return get_pre(node[p].l,x);
}
int get_nex(int p,int x){
if(!p)return INF;
else if(x<node[p].val)return comp(node[p].val,get_nex(node[p].l,x),0);
else return get_nex(node[p].r,x);
}
main program
int main(){
srand((unsigned int)time(0));
newnode(-INF),newnode(INF);
root=1,node[1].r=2;pushup(1);
scanf("%d",&N);
while(N--){
scanf("%d%d",&op,&q);
if(op==1){insert(root,q);}
if(op==2){erase(root,q);}
if(op==3){printf("%d\n",getrank(root,q)-1);}
if(op==4){printf("%d\n",getval(root,q+1));}
if(op==5){printf("%d\n",get_pre(root,q));}
if(op==6){printf("%d\n",get_nex(root,q));}
}
return 0;
}
Complete code
Do not copy directly
#include<bits/stdc++.h>
#define INF 0xffffffff
using namespace std;
int K,N,op,q,root;
struct Node{int val,l,r,cnt,size,f;}node[100039];
int comp(int a,int b,bool x){return x?(a>b?a:b):(a>b?b:a);}
int newnode(int x){node[++K].val=x,node[K].cnt=node[K].size=1;node[K].f=rand();return K;}
void pushup(int p){node[p].size=node[node[p].l].size+node[node[p].r].size+node[p].cnt;}
void zag(int &p){
int k=node[p].l;
node[p].l=node[k].r,node[k].r=p,p=k;
pushup(node[p].r),pushup(p);
}
void zig(int &p){
int k=node[p].r;
node[p].r=node[k].l,node[k].l=p,p=k;
pushup(node[p].l),pushup(p);
}
void insert(int &p,int x){
if(!p)p=newnode(x);
else if(x==node[p].val){node[p].cnt++,node[p].size++;}
else if(x<node[p].val){insert(node[p].l,x);if(node[node[p].l].f<node[p].f)zag(p);}
else if(x>node[p].val){insert(node[p].r,x);if(node[node[p].r].f<node[p].f)zig(p);}
pushup(p);
}
void erase(int &p,int x){
if(node[p].val==x){
if(node[p].cnt>1)node[p].cnt--;
else if(!node[p].l)p=node[p].r;
else if(!node[p].r)p=node[p].l;
else if(node[node[p].l].f<node[node[p].r].f)zag(p),erase(node[p].r,x);
else if(node[node[p].l].f>node[node[p].r].f)zig(p),erase(node[p].l,x);
}
else if(node[p].val>x)erase(node[p].l,x);
else if(node[p].val<x)erase(node[p].r,x);
pushup(p);
}
int getrank(int p,int x){
if(!p)return 0;
else if(node[p].val>x)return getrank(node[p].l,x);
else if(node[p].val<x)return getrank(node[p].r,x)+node[node[p].l].size+node[p].cnt;
else if(node[p].val==x)return node[node[p].l].size+1;
}
int getval(int p,int x){
if(x<=node[node[p].l].size+node[p].cnt&&x>node[node[p].l].size)return node[p].val;
else if(x<=node[node[p].l].size)return getval(node[p].l,x);
else return getval(node[p].r,x-node[node[p].l].size-node[p].cnt);
}
int get_pre(int p,int x){
if(!p)return -INF;
else if(x>node[p].val)return comp(node[p].val,get_pre(node[p].r,x),1);
else return get_pre(node[p].l,x);
}
int get_nex(int p,int x){
if(!p)return INF;
else if(x<node[p].val)return comp(node[p].val,get_nex(node[p].l,x),0);
else return get_nex(node[p].r,x);
}
int main(){
srand((unsigned int)time(0));
newnode(-INF),newnode(INF);
root=1,node[1].r=2;pushup(1);
scanf("%d",&N);
while(N--){
scanf("%d%d",&op,&q);
if(op==1){insert(root,q);}
if(op==2){erase(root,q);}
if(op==3){printf("%d\n",getrank(root,q)-1);}
if(op==4){printf("%d\n",getval(root,q+1));}
if(op==5){printf("%d\n",get_pre(root,q));}
if(op==6){printf("%d\n",get_nex(root,q));}
}
return 0;
}