程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 38G Queue 伸展樹

Codeforces 38G Queue 伸展樹

編輯：C++入門知識

Codeforces 38G Queue 伸展樹

題目鏈接：點擊打開鏈接

題意：

給定n個人來排隊

每個人有2個參數，身份優先級和臉皮厚度 ==

來的那個人會排到隊尾

如果這個人的優先級比他前面那個人的優先級大就會和前面那個人交換位置。

交換一次臉皮厚度減1，一直交換到隊頭或者臉皮厚度為0

交換完成後下一個人才會到來。

問：

隊伍最後的情況（從隊頭到隊尾依次輸出每個人的編號）

思路:splay

維護子樹的最小值。

插入時遞歸插入，若當前點是空就插這個位置。

然後就是裸的splay。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair pii;
#define ll int
#define inf 1000000
#define N 100005
#define L(x) tree[x].ch[0]
#define R(x) tree[x].ch[1]
#define Size(x) tree[x].siz
#define Val(x) tree[x].val
#define Father(x) tree[x].fa
#define Max(x) tree[x].max
struct node{
    int ch[2], siz, fa;
    int val, max; //伸展樹裡存的是隊列的順序
}tree[N];
int tot, root;
void Newnode(int &id, int fa, int val, int siz = 1){
    node E={0,0,siz,fa,val,val};
    id = tot++;
    tree[id] = E;
}
void push_down(int id){}
void push_up(int id){
    Size(id) = Size(L(id)) + Size(R(id)) + 1;
    Max(id) = max( max(Max(L(id)), Max(R(id))), Val(id));
}
void Rotate(int id, int kind){
    int y = Father(id);
    push_down(y); push_down(id);
    tree[y].ch[kind^1] = tree[id].ch[kind];
    Father(tree[id].ch[kind]) = y;
    if(Father(y))
        tree[Father(y)].ch[R(Father(y))==y] = id;
    Father(id) = Father(y);
    Father(y) = id;
    tree[id].ch[kind] = y;
    push_up(y);
}
void Splay(int id, int goal){
    push_down(id);
    while(Father(id) != goal)
    {
        int y = Father(id);
        if(Father(y) == goal)
            Rotate(id, L(y) == id);
        else
        {
            int kind = L(Father(y)) == y;
            if(tree[y].ch[kind]==id)
            {
                Rotate(id, kind^1);
                Rotate(id, kind);
            }
            else
            {
                Rotate(y, kind);
                Rotate(id, kind);
            }
        }
    }
    push_up(id);
    if(goal == 0)root = id;
}
void Insert(int &id, int val, int siz, int father){ //把值為val的點插到goal點後面
	if(id == 0) {
		Newnode(id, father, val);
		return ;
	}
	if(val < Max(R(id)) || val < Val(id) || siz < Size(R(id)))
		Insert(R(id), val, siz, id);
	else
		Insert(L(id), val, siz-Size(R(id))-1, id);
	push_up(id);
}

void init(){
    //初始化0這個點
    Father(0) = L(0) = R(0) = Size(0) = 0;
    Val(0) = 0;
    //默認1為最左端點
    tot = 1;
    Newnode(root, 0, inf);
    Newnode(R(root), root, -1);
    push_up(root);
}
mapmp;

void put(ll id){
    if(L(id))
        put(L(id));
    if(id > 2)
        printf("%d ",mp[Val(id)]);
    if(R(id))
        put(R(id));
}
int main(){
    ll i, u, v, n, id;
    while(cin>>n){
        mp.clear();
        init();
        for(i = 1; i <= n; i++) {
            scanf("%d %d", &u, &v);
			Insert(root, u, v, 0);
			Splay(tot-1, 0);
            mp[u] = i;
        }
        put(root); puts("");
    }
    return 0;
}
/*
2
1 0
2 1

3
1 3
2 3
3 3

5
2 3
1 4
4 3
3 1
5 2

1
1 0

4
4 1
2 2
1 3
3 2

4
4 1
2 2
1 3
3 1

4
4 1
2 2
1 3
3 0

4
1 0
2 1
3 2
4 3

4
1 0
2 1
4 2
3 3

5
1 0
2 1
4 2
3 3
5 2

6
1 0
2 1
4 2
3 3
5 2
6 4

7
2 2
3 4
5 1
7 2
6 5
1 0
4 1

ans:
1 4 2 3
1 2 4 3
1 2 3 4
4 3 2 1
3 4 2 1
3 4 5 2 1
3 6 4 5 2 1
2 4 5 3 1 7 6

*/