思路:
1.维护一个栈没什么好说的。
2.重点在实现一个数据结构能插入、删去一个数,并能查询到当前栈中第k大的值。
3.触发关键词:第k大。
4.那么我们可以用权值线段树或者树状数组都行,树状数组用二分锁定就行。
5.我做的时候题目没有给操作次数范围,假定操作m次
6.时间复杂度mlogn; 1 <= n <= 1e5;
思考:
1.本人在网上看到一种模拟做法。
2.用二分查询到>=x的边界,然后在x前面插入新加的数。
3.如果操作次数较大,插入操作应该是O(n)级别的,总体大概是O(nm).
4.感觉数据如果大一点可能会被卡。(但我没看到操作次数的范围)。
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
typedef long long LL;
const int N = 1e5 + 10;
// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;
// const int P = 1 << 10;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<LL, int> PLI;
typedef pair<int, string> PIS;
typedef pair<double, int> PDI;
typedef pair<string, int> PSI;
const double eps = 1e-4;
const int mod = 1e9 + 7;
int n, k;
int m;
int Q;
// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int tr[N];
int tt = 0;
int lowbit(int x)
{
return x & -x;
}
int query(int idx)
{
int res = 0;
for (int i = idx; i; i -= lowbit(i))
{
res += tr[i];
}
return res;
}
void add(int idx, int c)
{
for (int i = idx; i <= 1e5 + 10; i += lowbit(i))
{
tr[i] += c;
}
}
int find()
{
int l = 0;
int r = 1e5 + 10;
int tar = (tt + 1) / 2;
while (l + 1 < r)
{
int mid = l + r >> 1;
// cout << query(mid) << endl;
if (query(mid) >= tar)
{
r = mid;
}
else
{
l = mid;
}
}
return r;
}
void solve()
{
scanf("%d", &n);
vector<int> stk(n + 1);
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
if (s[1] == 'o')
{
if (tt > 0)
{
add(stk[tt], -1);
printf("%d\n", stk[tt--]);
}
else
{
puts("Invalid");
}
}
else if (s[1] == 'e')
{
if (tt > 0)
{
int ans = find();
printf("%d\n", ans);
}
else
{
// cout << i << ' ' << tt << endl;
puts("Invalid");
}
}
else
{
int x;
scanf("%d", &x);
stk[++tt] = x;
add(x, 1);
}
}
}
int main()
{
int t = 1;
// init(1000000);
// scanf("%d", &t);
// int a = 1;
// for (int i = 1; i <= 26; i++)
// {
// a = (a << 1) + 1;
// }
// cout << a << endl;
// float t = 134217727;
// int cnt = 200;
// printf("%.16lf", t);
// while (cnt--)
// {
// t = t * 2 + a;
// printf("%.16f\n", t);
// }
// getchar();
while (t--)
{
// cout << (2563 % 11) << endl;
// cout << t << endl;
solve();
// cout << (((float)1) << 63) << endl;
// cout << '\0' << endl;
// cout << f(4);
// cout<<(25 >> 5)
// cout << gcd(31415, 14142);//
// cout << (28284 / 11) << endl;
}
return 0;
}
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/