zerol edited 7 年，4 月前
方案1：再开一个 multiset 记录当前栈中的元素，以便查询最大元素，当然这么做平白无故多出了个常数的复杂度（$lgn$），虽然不影响AC。
方案2：再开一个 stack 用于存放最大元素，下面我粘贴一段英文题解（真·官方题解）
The approach is pretty straight forward. We keep two stacks: One is for pushing and popping elements as they come and go (elements stack), and the other is for keeping track of the maximum element (maximum elements stack).
When the first element arrives, push it onto both of the stacks. As the elements may not be distinct, we need to keep track of their indices. So, declare a stack of pair<int, int> or use a structure.
We maintain the maximum elements stack so that the maximum element till now is on the top. Whenever we push an element, it normally goes to the elements stack, but we also push it to the maximum elements stack if, and only if, it is greater than the current maximum element.
Now, when an element is to be deleted, we pop it directly from the elements stack. We also check if that particular element is the maximum element or not. We do so by comparing the value and the index of the popped element with the element on top of the maximum elements stack. If they are equal, we pop that element as well.
Finally, to answer the maximum element query 3, we print the element on top of the maximum elements stack.
参考入门经典P180
书上有核心代码，所以标程就不贴了。
这个太简单了，肯定难不住会逆波兰（后缀）表达式求值的你们。
如果感到疑惑请直接看代码。
单调栈。建议大家去网上搜一搜相关内容。
哈夫曼树。
具体请参考入门经典P234
这道题目有点难.
贴一个网上的题解
按照端点排序，然后再从左到右扫一遍，同时维护一个存放建筑高度的 multiset（遇到建筑的左端点便将其高度加入 set，遇到右端点便将其从 set 中移除），这样我们又能知道每两个端点间建筑的最高高度了。
set大法
#include <bits/stdc++.h>
using namespace std;
multiset<int> St;
stack<int> Sk;
int n, t, k;
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &t);
if (t == 1) {
scanf("%d", &k);
St.insert(k);
Sk.push(k);
} else if (t == 2) {
St.erase(St.find(Sk.top()));
Sk.pop();
} else {
printf("%d\n", *St.rbegin());
}
}
}
单调栈大法（官方题解）
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
int main()
{
stack<pair<int,int> > ele, maxi;
int n, i = 1;
cin>>n;
while(i <= n)
{
int t, v;
pair<int, int> p1, p2;
cin>>t;
if(t == 1)
{
cin>>v;
ele.push(make_pair(v, i));
if(maxi.size() == 0)
{
maxi.push(make_pair(v, i));
}
else
{
p1 = maxi.top();
if(p1.first < v)
{
maxi.push(make_pair(v, i));
}
}
}
else if(t == 2)
{
p1 = ele.top();
ele.pop();
p2 = maxi.top();
if(p1.first == p2.first && p1.second == p2.second)
{
maxi.pop();
}
}
else
{
p1 = maxi.top();
cout<<p1.first<<endl;
}
i++;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
char s[2000];
int T;
map<char, char> mp;
bool check() {
stack<char> Sk;
int n = strlen(s);
for (int i = 0; i < n; ++i) {
if (mp.count(s[i])) {
if (!Sk.empty() && Sk.top() == mp[s[i]]) Sk.pop();
else return false;
} else Sk.push(s[i]);
}
if (Sk.empty()) return true;
return false;
}
int main() {
mp[')'] = '('; mp['}'] = '{'; mp[']'] = '[';
#ifdef zerol
freopen("in", "r", stdin);
#endif
scanf("%d", &T);
while(T--) {
scanf("%s", s);
if (check()) puts("YES");
else puts("NO");
}
}
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1E6 + 100;
int n, a[maxn], ans[maxn];
stack<int> S;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = n - 1; i >= 0; --i) {
while (!S.empty() && a[S.top()] <= a[i]) S.pop();
if (S.empty()) ans[i] = -1;
else ans[i] = S.top();
S.push(i);
}
for (int i = 0; i < n; ++i)
printf("%d\n", ans[i] + 1);
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, k;
LL ans;
priority_queue<LL, vector<LL>, greater<LL>> pq;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &k);
pq.push(k);
}
if (n != 1)
while (1) {
LL t = pq.top(); pq.pop();
t += pq.top(); pq.pop();
ans += t;
if (pq.empty()) break;
pq.push(t);
}
printf("%lld\n", ans);
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e14 + 7;
struct Node {
int x, h;
int type;
bool operator < (const Node &u) const {
return x < u.x;
}
};
int n;
Node a[100000];
int main() {
#ifdef ULTMASTER
freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[2 * i] = (Node){x, z, 1};
a[2 * i + 1] = (Node){y, z, 0};
}
sort(a, a + 2 * n);
multiset<int> ms;
ll ans = 0;
// for (int i = 0; i < 2 * n; ++i)
// printf("%d %d\n", i, a[i].x);
for (int i = 0; i < 2 * n; ++i) {
if (!ms.empty()) {
// printf("%d %d %d %d %d\n", i, a[i].x, a[i-1].x, *ms.rbegin(), ms.size());
ans += 1LL * (a[i].x - a[i - 1].x) * (*ms.rbegin());
}
if (a[i].type == 1)
ms.insert(a[i].h);
else
ms.erase(ms.find(a[i].h));
}
printf("%lld\n", ans);
return 0;
}