Solve

NOI2004郁闷的出纳员

题目解答

这是一道考察数据结构的题目，理论上使用静态的会更好，不见得动态的就快，但是我是使用Treap AC的。原理很简单，就是需要额外再用一个delta来记录差量，避免Treap退化，所以在加入一个节点时 ，要减去这个差量，最后输出时加上即可。然后’S’、’A’操作只改变delta，剩下的就是实现了。

运行情况

自己测试AC，此刻NOI的那个OJ挂了 = =|||

NOI 2004

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<fstream>
#include<ctime>
#include<cmath>
using namespace std;
ifstream fin("test.in");
ofstream fout("test.out");
long n,minx,k,delta=0,tot;
struct node{
    long weight,value,size;
    node *left,*right;//不必记录祖先
}*root,*son;//建立超级父亲,超级子孙
class bst{
    public:
    inline node *newnode(long key)
    {
	tot++;
        node *tnode=new node;
        tnode->value=key;
        tnode->weight=abs(rand());
        tnode->left=son;
        tnode->right=son;
		Refresh(tnode);
        return tnode;
    }
    inline void Refresh(node *tree){tree->size=tree->left->size+tree->right->size+1;}
    inline node* leftrotate(node *tree)
    {
        node *T=tree->right;
        tree->right=T->left;
        T->left=tree;
        Refresh(tree);Refresh(T);
        return T;
    }
    inline node *rightrotate(node *tree)
    {
        node *T=tree->left;
        tree->left=T->right;
        T->right=tree;
        Refresh(tree);Refresh(T);
        return T;
    }
    node *insert(node *ins,node *index)
    {
        if(ins->value<=index->value)
        {
            if(index->left==son) index->left=ins;
            else index->left=insert(ins,index->left);//更新子节点
            if(index->weight>index->left->weight) index=rightrotate(index);//更新父节点
        }
        else
        {
            if(index->right==son) {index->right=ins;}
            else index->right=insert(ins,index->right);//更新子节点
            if(index->weight>index->right->weight) index=leftrotate(index);//更新父节点
        }
        Refresh(index);//refresh
        return index;
    }
    inline long findk(long rank)
    {
        node *temp=root->left;
	if(temp->size<rank) return -1;
        while(rank!=temp->size-temp->left->size)
        {
            if(rank<temp->size-temp->left->size) temp=temp->right;
            else {rank-=temp->size-temp->left->size;temp=temp->left;}
        }
        return temp->value;
    }
    void tdelete(long key,node *del)//a whole subtree
    {
        if(del->left!=son)
        	if(del->left->value+delta<key)
		{
			del->left=del->left->right;
			Refresh(del);
			tdelete(key,del);
			Refresh(del);
		}
		else {tdelete(key,del->left);Refresh(del);}
	else return ;
    }
}treap;
int main()
{
	char op;
    srand((unsigned)time(0));
    son=new node;
    root=new node;
    son->weight=99999999;
    son->size=0;
    root->weight=-1;
    root->left=son;
    root->right=son;
    root->value=99999999;
    root->size=1;
	fin>>n>>minx;
    for(long i=1;i<=n;i++)
	{
		fin>>op;
		switch(op)
		{
			case('I'):
				fin>>k;
				if(k>=minx) treap.insert(treap.newnode(k-delta),root);
				break;
			case('S'):
				fin>>k;
				delta-=k;
				treap.tdelete(minx,root);
				break;
			case('A'):
				fin>>k;
				delta+=k;
				break;
			case('F'):
				fin>>k;
				k=treap.findk(k);
				if(k==-1) fout<<-1<<endl;
				else fout<<k+delta<<endl;
				break;
		}
	}
	fout<<tot-root->size+1<<endl;
    return 0;
}

难易等级

Medium (NOI the 1st)