L3-2. 堆栈（线段树）

L3-2. 堆栈（线段树）

L3-2. 堆栈

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。

输入格式：

输入第一行给出正整数N（<= 105）。随后N行，每行给出一个操作指令，为下列3种指令之一：

Push

key

Pop

PeekMedian

其中Push表示入栈，key是不超过105的正整数；Pop表示出栈；PeekMedian表示查中值。

输出格式：

对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“Invalid”。

输入样例：

17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop

输出样例：

Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid

题解：用线段树解决，单点更新查询，用线段树，保存本区间内的点数

AC代码：

#include#include#include#include#include#define lson l,m,level*2#define rson m+1,r,level*2+1using namespace std;int a[100010];int tree[100010*5];//单点更新查询，用线段树，保存本区间内的点数void init(int l,int r,int level);void find(int l,int r,int level,int x);void update(int l,int r,int level,int x,int s);int main(){ int N; scanf("%d",&N); stacks; getchar(); int mmax = 100002; memset(a,0,sizeof(a)); memset(tree,0,sizeof(tree)); while(N--){ char c[30]; int num; scanf("%s",c); if(!strcmp(c,"Pop")){ if(!s.empty()){ printf("%d\n",s-()); update(1,mmax,1,s-(),0); a[s-()]--; s.pop(); } else{ printf("Invalid\n"); } } else if(!strcmp(c,"PeekMedian")){ int n = s.size(); if(n>0){ if(n%2==1){ //注意奇偶数 n++; } find(1,mmax,1,n/2); } else{ printf("Invalid\n"); } } else if(!strcmp(c,"Push")){ scanf("%d",&num); s.push(num); a[num]++; if(mmax>1; if(x<=m){ update(lson,x,b); } else{ update(rson,x,b); } tree[level] = tree[level*2+1] + tree[level*2];}void find(int l,int r,int level,int x){ if(l==r&&(x<=tree[level])){ printf("%d\n",l); return ; } int m = (l+r)>>1; if(tree[level*2]>=x){ find(lson,x); } else{ find(rson,(x-tree[level*2])); }}void init(int l,int r,int level){ if(l==r){ tree[level] = a[l]; return ; } int m = (l+r)>>1; init(lson); init(rson); tree[level] = tree[level*2] + tree[level*2+1];}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。