VIJOS P1647 不差钱 SBT

不差钱

描述

同学们一起看了小品《不差钱》，LX神突发奇想，想刁难一下十八居士，他让十八居士模拟一下点菜的过程。

输入格式

输入第一行为一个数price，表示价钱大于price的菜赵本山都不要。

以下几行表示点菜的过程，每行两个整数p，n

p=1 表示在菜谱中添加一个价格为n的菜,这是第i个1号命令，这个菜的编号就是i，

p=2 表示菜谱中第n号菜已卖完（但不代表菜谱中没有了这种菜），

p=3 表示赵本山点第n贵的菜。

输入文件以0结束。

菜的价格0<n<=10^6。

3种命令， 30%数据命令最多300次， 60%数据命令最多3000次， 100%数据命令最多100000次。

输出格式

对于每个p=3， 如果第n贵的菜价格高于price，则输出“Dui bu qi,Mei you.”。

如果第n贵的菜价格不高于price，且没有卖完，则输出“You.”然后输出价格” m Yuan.”；

如果已卖完，则输出“Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!”

输入样例

40
1 41
1 39
1 100
1 204
1 1
1 27
1 18
1 79
3 1
3 2
3 5
2 5
3 8
2 7
3 7
1 10
3 8
0

输出样例

Dui bu qi,Mei you.
Dui bu qi,Mei you.
You. 39 Yuan.
Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!
Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!
You. 10 Yuan.

分析

题目意思表达得比较明确，本题也很适合作为SBT的模板题。

菜的编号就是存在SBT静态数组中的下标，只要加一个是否empty的标记即可。

唯一稍微可能有点问题的是出现多个相同菜价的菜时的选择问题，一开始按照普通二叉树的写法写SBT的前趋后继，后来发现这样做其实是不严谨的，因为左右旋操作的存在，虽然一开始相等的数是插入到右边去，但是不能保证不会因为左旋而把父节点旋到左子树去了，所以最后只能保证左子树的值不大于根，右子树的值不小于根，相等值是完全没办法判断的。

可能还是我的SBT写法不够严谨

……最后只好继续查找第n-1大、n-2大…第n+1大、第n+2大…直到找到不相等为止，O（k*logn）遍历一遍相等的数。

好在测试时间上好像还不错，不知道又没有更好的办法？

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : VIJOS1647
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 100010

typedef struct sbtnod
{
    int key,left,right,size;
    bool empty;
} sbtnode;
int sbttail,sbt;

sbtnode tree[MAXN];

void rrotate(int& t)
{
    int k=tree[t].left;
    if (!k) return ;
    tree[t].left=tree[k].right;
    tree[k].right=t;
    tree[k].size=tree[t].size;
    tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+1;
    t=k;
}

void lrotate(int& t)
{
    int k=tree[t].right;
    if (!k) return ;
    tree[t].right=tree[k].left;
    tree[k].left=t;
    tree[k].size=tree[t].size;
    tree[t].size=tree[tree[t].left].size+tree[tree[t].right].size+1;
    t=k;
}

void maintain(int& t,bool flag)
{
    if (!t) return ;
    if (!flag)
        if (tree[tree[tree[t].left].left].size>tree[tree[t].right].size) rrotate(t);
        else if (tree[tree[tree[t].left].right].size>tree[tree[t].right].size) 
        {
            lrotate(tree[t].left);
            rrotate(t);
        } else return ;
    else
        if (tree[tree[tree[t].right].right].size>tree[tree[t].left].size) lrotate(t);
        else if (tree[tree[tree[t].right].left].size>tree[tree[t].left].size)
        {
            rrotate(tree[t].right);
            lrotate(t);
        } else return ;
    
    maintain(tree[t].left,false);
    maintain(tree[t].right,true);
    maintain(t,false);
    maintain(t,true);
}

void insert(int& t,int v)
{
    if (!t)
    {
        sbttail++;
        tree[sbttail].key=v;
        tree[sbttail].size=1;
        tree[sbttail].empty=false;
        t=sbttail;
    } else 
    {
        tree[t].size++;
        if (v<tree[t].key) insert(tree[t].left,v);
        else insert(tree[t].right,v);
        maintain(t,v>=tree[t].key);
    }
}

int select(int t,int k)
{
    if (k==tree[tree[t].left].size+1) return t;
    if (k<=tree[tree[t].left].size) return select(tree[t].left,k);
    else return select(tree[t].right,k-1-tree[tree[t].left].size);
}

int main()
{
    freopen("1.txt","r",stdin);
    
    int pri;
    scanf("%d",&pri);

    sbt=0;
    sbttail=0;

    int p,n;
    while(scanf("%d%d",&p,&n)==2)
    {
        switch(p)
        {
            case 1:
                insert(sbt,n);
                break;
            case 2:
                tree[n].empty=true;
                break;
            case 3:
                n=sbttail-n+1;
                int temp=select(sbt,n);
                if (tree[temp].key>pri) printf("Dui bu qi,Mei you.\n");
                else
                {
                    bool done=false;
                    if (!tree[temp].empty) 
                    {
                        done=true;
                        printf("You. %d Yuan.\n",tree[temp].key);
                    } else 
                    {
                        int pre,p=n;
                        while(p>1&&(!done))
                        {
                            p--;
                            pre=select(sbt,p);
                            if (tree[pre].key<tree[temp].key) break;
                            if (!tree[pre].empty)
                            {
                                done=true;
                                printf("You. %d Yuan.\n",tree[temp].key);
                            }
                        }
                        int suc,s=n;
                        while(s<n&&(!done))
                        {
                            s++;
                            suc=select(sbt,s);
                            if (tree[suc].key>tree[temp].key) break;
                            if (!tree[suc].empty)
                            {
                                done=true;
                                printf("You. %d Yuan.\n",tree[temp].key);
                            }
                        }
                    }
                    if (!done) printf("Mei you. Zhe ge ke yi you. Zhe ge zhen mei you!\n");
                }
        }
    }

    return 0;
}