L3-002. 堆栈

模拟堆栈+树状数组



const int maxn = 1e5+10;
int tree[maxn];
int a[maxn];
void Add(int x,int p)//
{
    while(x < maxn)
        {
            tree[x] += p;
            x += lowbit(x);
        }
}
int Query(int x)
{
    int sum = 0;
    while(x)
    {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}
int main(void)
{
	// freopen("input.txt","r",stdin);
	int l,r;
	l = r = 0;
	int n;cin>>n;
	getchar();
	while(n--){
		string s;
		getline(cin,s);

		if(s[1] == 'o'){
			if(r == l)
				puts("Invalid");
			else{
				printf("%d\n",a[--r]);
				Add(a[r],-1);
			}
		}
		else if(s[1] == 'e'){
			if(l == r)
				puts("Invalid");
			else{
				int L = 1,R = 1e5;
				int num = (r+1)/2;
				// DEBUG;
				// cout<<num<<endl;
				// cout<<Query(3)<<endl;
				while(R >= L){
					int mid = (R+L)/2;
					if(Query(mid) < num)
						L = mid+1;
					else
						R = mid-1;

				}	
				printf("%d\n",L);
			}
		}
		else{
			char ar[100];int aa;
			sscanf(s.c_str(),"%s %d",ar,&aa);
			// cout<<a<<endl;
			a[r++] = aa;
			Add(aa,1);
		}
	}
    

   return 0;
}