ECNUOJ 2149 华丽的队列

华丽的队列

Time Limit:3000MS Memory Limit:65536KB
Total Submit:531 Accepted:68

Description

每年,都有很多新同学来到我们学校,最近,我们学校的领导为了考验新同学的能力,想出了一个方法来测试:
领导们定义了一个队列,队列中的元素是顺序存放的,领导们还定义了队列的几种操作:
a) insert x ,向队列末尾添加一个元素x
b) delete ,删除队列前的第一个元素
c) MinElement 删除队列中的最小元素
HINT:
1.insert的元素x(0<=x<=1000000)
2.队列中的元素是唯一的,不会出现重复元素
3.对于每组测试数据,操作的数量(0<=op<=50000)

Input

首先一个正整数N,代表操作的数量:
接下来从2到N+1行:
每行开始一个字符串s,有3种字符串: insert , delete 或者 MinElement
对于insert 接下来有个整数x,代表插入队列的元素
对于delete ,删除队首的元素
对于MinElement , 返回队列中的最小元素,并且把这个元素从队列中删除

Output

对于每个操作,输出不同的答案:

对于insert ,输出队列中元素的总数n
对于delete ,删除队首的元素,并且输出这个队首元素x
对于MinElement , 输出队列中的最小元素x.并且把这个元素从队列中删除

Sample Input

6
insert 1
insert 2
insert 3
insert 4
delete
MinElement

Sample Output

1
2
3
4
1
2

Source

华丽的队列

解题：没找到别的方法，只好强行上线段树了。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 struct node {

     int lt,rt,minv;

 } tree[maxn<<];

 int ret;

 void build(int lt,int rt,int v) {

     tree[v].lt = lt;

     tree[v].rt = rt;

     tree[v].minv = INF;

     if(lt == rt) return;

     int mid = (lt + rt)>>;

     build(lt,mid,v<<);

     build(mid+,rt,v<<|);

 }

 void update(int lt,int rt,int v,int val) {

     if(lt <= tree[v].lt && rt >= tree[v].rt) {

         ret = tree[v].minv;

         tree[v].minv = val;

         return ;

     }

     if(lt <= tree[v<<].rt) update(lt,rt,v<<,val);

     if(rt >= tree[v<<|].lt) update(lt,rt,v<<|,val);

     tree[v].minv = min(tree[v<<].minv,tree[v<<|].minv);

 }

 int head(int v) {

     if(tree[v].lt == tree[v].rt) {

         return tree[v].lt;

     }

     if(tree[v<<].minv < INF) return head(v<<);

     if(tree[v<<|].minv < INF) return head(v<<|);

 }

 int tail(int v) {

     if(tree[v].lt == tree[v].rt) return tree[v].lt;

     if(tree[v<<|].minv < INF) return tail(v<<|);

     if(tree[v<<].minv < INF) return tail(v<<);

 }

 int themin(int v) {

     if(tree[v].lt == tree[v].rt) return tree[v].lt;

     if(tree[v<<].minv < tree[v<<|].minv) return themin(v<<);

     if(tree[v<<|].minv < tree[v<<].minv) return themin(v<<|);

 }

 int main() {

     int m,val,siz = ,h;

     char op[];

     scanf("%d",&m);

     build(,,);

     while(m--) {

         scanf("%s",op);

         if(op[] == 'i') {

             scanf("%d",&val);

             if(siz == ) {

                 update(,,,val);

             } else {

                 h = tail();

                 update(h+,h+,,val);

             }

             siz++;

             printf("%d\n",siz);

         } else if(op[] == 'd') {

             h = head();

             update(h,h,,INF);

             printf("%d\n",ret);

             siz--;

         } else if(op[] == 'M') {

             h = themin();

             update(h,h,,INF);

             printf("%d\n",ret);

             siz--;

         }

     }

     return ;

 }

巴特西

ECNUOJ 2149 华丽的队列

最新文章

热门文章