题解
第一种方法: 令数组 tree[] 记录栈中的元素, 栈中的数值 x 的个数为 tree[x] . 树状数组维护 tree[], 然后二分查找.
第二种方法: 利用分块, 以一定长度区间为单位, 记录栈中数值的个数, 然后暴力查找.
代码
- // 树状数组 + 二分
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=100010;
- int tree[maxn];
- stack<int> sta;
- void update(int p,int w);
- int sum(int p);
- int main()
- {
- int n,w,left,right,mid,k;
- string op;
- scanf("%d",&n);
- while(n--)
- {
- cin>>op;
- if(op[1]=='u')
- {
- scanf("%d",&w);
- sta.push(w);
- update(w,1);
- }
- else
- {
- if(sta.size()<1) printf("Invalid\n");
- else if(op[1]=='o')
- {
- printf("%d\n",sta.top());
- update(sta.top(),-1);
- sta.pop();
- }
- else
- {
- left=0;right=maxn;k=(sta.size()+1)/2;
- while(left<=right)
- {
- mid=(left+right)/2;
- if(sum(mid)>=k) right=mid-1;
- else left=mid+1;
- }
- printf("%d\n",left);
- }
- }
- }
- system("pause");
- return 0;
- }
- void update(int p,int w)
- {
- for(;p<maxn;p += p&(-p))
- tree[p]+=w;
- }
- int sum(int p)
- {
- int ans=0;
- for(;p>0;p -= p&(-p))
- ans+=tree[p];
- return ans;
- }
- // 分块
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=100010,block_size=367;
- int cnt[maxn],block[280];
- stack<int> sta;
- void PUSH_POP(int index,int v);
- int Find(int k);
- int main()
- {
- int n,w;
- string op;
- scanf("%d",&n);
- while(n--)
- {
- cin>>op;
- if(op[1]=='u')
- {
- scanf("%d",&w);
- sta.push(w);
- PUSH_POP(w,1);
- }
- else
- {
- if(sta.size()<1) printf("Invalid\n");
- else if(op[1]=='o')
- {
- printf("%d\n",sta.top());
- PUSH_POP(sta.top(),-1);
- sta.pop();
- }
- else printf("%d\n",Find((sta.size()+1)/2));
- }
- }
- system("pause");
- return 0;
- }
- void PUSH_POP(int index,int v)
- {
- cnt[index]+=v;
- block[index/block_size]+=v;
- }
- int Find(int k)
- {
- int sum=0,i=0,index;
- while(sum + block[i] <k)
- sum+=block[i++];
- index=block_size*i;
- while(1)
- {
- if(sum + cnt[index]>= k) return index;
- else sum+=cnt[index],index++;
- }
- }
来源: http://www.bubuko.com/infodetail-3394563.html