3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 19122 Solved: 8359
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
分析
学了一个神奇的平衡树，叫：finger tree
贴一下模板。。
code
#include<cstdio>
#include<algorithm>
#define ls ch[cur][0]
#define rs ch[cur][1] using namespace std; const int N = ; int siz[N],val[N],ch[N][],q[N];
int tot,cnt,Root; int getid() {
return tot?q[tot--]:++cnt;
}
void pushup(int cur) {
if (!siz[ls]) return; // -
siz[cur] = siz[ls] + siz[rs];
val[cur] = val[rs];
}
int newNode(int v) {
int cur = getid();
siz[cur] = ;val[cur] = v;
ls = rs = ;
return cur;
}
void copyNode(int x,int y) {
ch[x][] = ch[y][];ch[x][] = ch[y][];
siz[x] = siz[y];val[x] = val[y];
}
int Merge(int x,int y) {
int cur = getid();
val[cur] = val[y];siz[cur] = siz[x]+siz[y]; //---
ls = x;rs = y;
return cur;
}
void lturn(int cur) {
ls = Merge(ls,ch[rs][]);
q[++tot] = rs;
rs = ch[rs][];
}
void rturn(int cur) {
rs = Merge(ch[ls][],rs);
q[++tot] = ls;
ls = ch[ls][];
}
void Maintain(int cur) {
if (rs && siz[ls] > siz[rs] * ) rturn(cur);
if (ls && siz[rs] > siz[ls] * ) lturn(cur);
}
void Insert(int cur,int x) {
if (siz[cur]==) {
ls = newNode(min(val[cur],x));
rs = newNode(max(val[cur],x));
pushup(cur);
return ;
}
if (x > val[ls]) Insert(rs,x);
else Insert(ls,x);
pushup(cur);
Maintain(cur);
}
void Delete(int cur,int fa,int x) {
if (siz[cur]==) {
if (ch[fa][] == cur) copyNode(fa,ch[fa][]); //-----
else copyNode(fa,ch[fa][]);
return;
}
fa = cur;
if (x > val[ls]) Delete(rs,cur,x);
else Delete(ls,cur,x);
pushup(cur);
Maintain(cur);
}
int getrnk(int cur,int x) {
if (siz[cur]==) return ;
//{
// if (x > val[cur]) return 2;
// return 1;
//}
if (x > val[ls])
return getrnk(rs,x) + siz[ls];
else return getrnk(ls,x);
}
int getkth(int cur,int k) {
if (siz[cur]==k) return val[cur];
if (k > siz[ls])
return getkth(rs,k-siz[ls]);
else return getkth(ls,k);
}
int main () {
int T;
scanf("%d",&T);
Root = newNode(1e9);
while (T--) {
int opt,x;
scanf("%d%d",&opt,&x);
if (opt==) Insert(Root,x);
else if (opt==) Delete(Root,Root,x);
else if (opt==) printf("%d\n",getrnk(Root,x));
else if (opt==) printf("%d\n",getkth(Root,x));
else if (opt==) printf("%d\n",getkth(Root,getrnk(Root,x)-));
else printf("%d\n",getkth(Root,getrnk(Root,x+))); // ---
}
return ;
}
模板的变迁史：
#include<cstdio>
#include<algorithm> using namespace std; const int N = ; int siz[N],val[N],ch[N][];
int q[N],tot;
int cnt;
int Root; int getid() {
return tot?q[tot--]:++cnt;
}
void pushup(int x) {
if (!siz[ch[x][]]) return; // -
siz[x] = siz[ch[x][]] + siz[ch[x][]];
val[x] = val[ch[x][]];
}
int newNode(int v) {
int cur = getid();
siz[cur] = ;val[cur] = v;
ch[cur][] = ch[cur][] = ;
return cur;
}
void copyNode(int x,int y) {
ch[x][] = ch[y][];ch[x][] = ch[y][];
siz[x] = siz[y];val[x] = val[y];
}
int merge(int x,int y) {
int cur = getid();
val[cur] = val[y];siz[cur] = siz[x]+siz[y]; //---
ch[cur][] = x;ch[cur][] = y;
return cur;
}
void lturn(int cur) {
ch[cur][] = merge(ch[cur][],ch[ch[cur][]][]);
q[++tot] = ch[cur][];
ch[cur][] = ch[ch[cur][]][];
}
void rturn(int cur) {
ch[cur][] = merge(ch[ch[cur][]][],ch[cur][]);
q[++tot] = ch[cur][];
ch[cur][] = ch[ch[cur][]][];
}
void maintain(int cur) {
if (ch[cur][] && siz[ch[cur][]] > siz[ch[cur][]] * ) rturn(cur);
if (ch[cur][] && siz[ch[cur][]] > siz[ch[cur][]] * ) lturn(cur);
}
void Insert(int cur,int x) {
if (siz[cur]==) {
ch[cur][] = newNode(min(val[cur],x));
ch[cur][] = newNode(max(val[cur],x));
pushup(cur);
return ;
}
if (x > val[ch[cur][]]) Insert(ch[cur][],x);
else Insert(ch[cur][],x);
pushup(cur);
maintain(cur);
}
void Delete(int cur,int fa,int x) {
if (siz[cur]==) {
if (ch[fa][] == cur) copyNode(fa,ch[fa][]); //-----
else copyNode(fa,ch[fa][]);
return;
}
fa = cur;
if (x > val[ch[cur][]]) Delete(ch[cur][],cur,x);
else Delete(ch[cur][],cur,x);
pushup(cur);
maintain(cur);
}
int rnk(int cur,int x) {
if (siz[cur]==) return ;
//{
// if (x > val[cur]) return 2;
// return 1;
//}
if (x > val[ch[cur][]])
return rnk(ch[cur][],x) + siz[ch[cur][]];
else return rnk(ch[cur][],x);
}
int kth(int cur,int k) {
if (siz[cur]==k) return val[cur];
if (k > siz[ch[cur][]])
return kth(ch[cur][],k-siz[ch[cur][]]);
else return kth(ch[cur][],k);
}
int main () {
int T;
scanf("%d",&T);
Root = newNode(1e9);
while (T--) {
int opt,x;
scanf("%d%d",&opt,&x);
if (opt==) Insert(Root,x);
else if (opt==) Delete(Root,Root,x);
else if (opt==) printf("%d\n",rnk(Root,x));
else if (opt==) printf("%d\n",kth(Root,x));
else if (opt==) printf("%d\n",kth(Root,rnk(Root,x)-));
else printf("%d\n",kth(Root,rnk(Root,x+))); // ---
}
return ;
}
指针
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream> using namespace std; const int MAXN = ; struct Node {
int val,size;
Node *ls,*rs;
Node():val(),size(),ls(NULL),rs(NULL) { }
Node(int v,int s,Node *l,Node *r) {
val = v,size = s,ls = l,rs = r;
}
bool isleaf() {
return ls == NULL;
}
void pushup() {
if (!isleaf()) {
size = ls->size + rs->size;
val = max(ls->val,rs->val);
}
}
}pool[MAXN]; Node *newNode(int val,int size,Node *ls,Node *rs) {
static int cnt = ;
pool[cnt] = Node(val,size,ls,rs);
return &pool[cnt++];
} void insert(Node *&cur,int x) {
if (cur==NULL) cur = newNode(x,,NULL,NULL);
else {
if (cur->isleaf()) {
cur->ls = newNode(min(x,cur->val),,NULL,NULL);
cur->rs = newNode(max(x,cur->val),,NULL,NULL);
}
else {
if (x > cur->ls->val) insert(cur->rs,x);
else insert(cur->ls,x);
}
cur -> pushup();
}
}
void erase(Node *cur,Node *fa,int x) {
if (cur->isleaf()) {
if (fa->ls == cur) *fa = *fa->rs;
else *fa = *fa->ls;
}
else {
if (x > cur->ls->val) erase(cur->rs,cur,x);
else erase(cur->ls,cur,x);
cur -> pushup();
}
}
int rnk(Node *cur,int x) {
if (cur->isleaf()) {
if (x > cur->val) return ;
return ;
}
else {
if (x > cur->ls->val)
return rnk(cur->rs,x)+cur->ls->size;
else return rnk(cur->ls,x);
}
}
int kth(Node *cur,int k) {
if (cur->isleaf()) return cur->val;
else {
if (k > cur->ls->size)
return kth(cur->rs,k - cur->ls->size);
else return kth(cur->ls,k);
}
}
int main () {
int T;
scanf("%d",&T);
Node *root = NULL;
while (T--) {
int opt,x;
scanf("%d%d",&opt,&x);
if (opt==) insert(root,x);
else if (opt==) erase(root,root,x);
else if (opt==) printf("%d\n",rnk(root,x));
else if (opt==) printf("%d\n",kth(root,x));
else if (opt==) printf("%d\n",kth(root,rnk(root,x)-));
else printf("%d\n",kth(root,rnk(root,x+)));
}
return ;
}