前言
noip毒瘤给我们讲上午的知识
知识总结
题目
T1 【模板】单调栈
题目描述
题目描述：
给出项数为 n 的整数数列 a1…n，定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，即 f(i)=min i<j<=n,aj>ai {j}。若不存在，则 f(i)=0。
试求出 f(1…n)。
输入格式：
第一行一个正整数 n。
第二行 n 个正整数 a1…n。
输出格式；
一行 n 个整数 f(1…n) 的值。
样例输入：
5
1 4 2 3 5
样例输出：
2 5 4 5 0
数据规模：
$n≤3*106$，$a_i≤1*109$。
思路解析
单调栈的简单运用。
考虑维护一个单调递减的栈。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
int n, a[N], f[N];
stack<int> s;
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = n; i >= 1; i--) {
while (!s.empty() && a[s.top()] <= a[i]) {
s.pop();
}
if (!s.empty()) {
f[i] = s.top();
}
s.push(i);
}
for (int i = 1; i <= n; i++) {
printf("%d ", f[i]);
}
return 0;
}
T2 动物园的等待
题目描述
https://www.luogu.com.cn/problem/P1823
思路解析
只考虑每个人与其前面的人产生的数对。
维护一个自下而上递减的栈。
在弹出的过程中，记录答案即可。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int v, id;
};
stack<node> s;
int n, h, ans;
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &h);
node now = {h, 1};
for (; !s.empty() && s.top().v <= h; s.pop()) {
ans += s.top().id;
if (s.top().v == h)
now.id += s.top().id;
}
if (!s.empty()) {
ans++;
}
s.push(now);
}
printf("%lld\n", ans);
return 0;
}
T3 雨点
题目描述
https://www.luogu.com.cn/problem/P2698
思路解析
首先注意到答案一定是在端点上，否则出头的部分就被浪费了。
按 x 排序后时间差等价于 y 的极差。
考虑二分答案后用单调队列或者 ST 表维护极差。
不用二分答案也可以直接用双指针+单调队列去维护。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000;
const ll INF = 1e18;
ll n, D;
pair<ll, ll> a[maxn + 50];
#define x first
#define y second
int q1[maxn + 50], q2[maxn + 50];
int h1 = 1, t1 = 0;
int h2 = 1, t2 = 0;
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> D;
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
ll ans = INF;
for (int i = 1, j = 1; i <= n; i++) {
for (; h1 <= t1 && q1[h1] < i;)
h1++;
for (; h2 <= t2 && q2[h2] < i;)
h2++;
bool flag = false;
for (; j <= n; j++) {
if (h1 > t1 || h2 > t2) {
q1[++t1] = j;
q2[++t2] = j;
continue;
}
if (a[q1[h1]].y - a[q2[h2]].y >= D) {
flag = true;
break;
}
for (; h1 <= t1 && a[q1[t1]].y <= a[j].y;)
t1--;
for (; h2 <= t2 && a[q2[t2]].y >= a[j].y;)
t2--;
q1[++t1] = j;
q2[++t2] = j;
}
if (!flag)
break;
ans = min(ans, abs(a[i].x - a[j - 1].x));
}
if (ans == INF)
cout << -1 << "\n";
else
cout << ans << "\n";
return 0;
}
T4 jxcakak
题目描述
P2216 HAOI2007 理想的正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路解析
最大值和最小值是独立的，可以单独求解。
考虑用单调队列去维护最大/小值，分行和列依次处理。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, inf = 0x3f3f3f3f;
int a[N][N], w, h, n, ans = inf;
struct node {
int h, t, pos[N], val[N], flag;
void init(int f) {
memset(pos, 0, sizeof(pos));
memset(val, 0, sizeof(val));
h = 1;
t = 0;
flag = f;
return;
}
void pop_front(int lim) {
for (; h <= t && pos[h] <= lim;)
h++;
}
void push_back(int p, int v) {
for (; h <= t && (val[t] - v) * flag <= 0;)
t--;
t++;
pos[t] = p;
val[t] = v;
return;
}
int get_first() {
return val[h];
}
} colmx[N], colmn[N], rowmx, rowmn;
signed main() {
scanf("%d%d%d", &w, &h, &n);
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= h; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= w; i++) {
colmx[i].init(1);
colmn[i].init(-1);
}
for (int j = 1; j <= h; j++) {
for (int i = 1; i <= w; i++) {
colmx[i].pop_front(j - n);
colmn[i].pop_front(j - n);
colmx[i].push_back(j, a[i][j]);
colmn[i].push_back(j, a[i][j]);
}
if (j >= n) {
rowmx.init(1);
rowmn.init(-1);
for (int i = 1; i <= w; i++) {
rowmx.pop_front(i - n);
rowmn.pop_front(i - n);
rowmx.push_back(i, colmx[i].get_first());
rowmn.push_back(i, colmn[i].get_first());
if (i >= n)
ans = min(ans, rowmx.get_first() + rowmn.get_first());
}
}
}
printf("%d", ans);
return 0;
}
T5 泽泽在英国
题目描述
泽泽用了100000000000000000000 mod 10天的时间爬出了长城。长城的另一端是一条隧道，泽泽走了进去……
泽泽不小心又到了英国。英国多雨，基本上隔2天就要下一场雨。泽泽人品不好，到这里的时候天正在下酸雨。
酸雨会腐蚀建筑物，让那些建筑物显得很难看。英国有家工厂免费为一条街道的建筑物的墙面涂油漆。心肠虽好，但是由于技术问题，他们只能涂出一个矩形。现在由于酸雨事态严重，街道办主任下命令涂出面积最大的矩形。
街道上的建筑物高度参差不齐，那该怎么办呢？
他们想到了泽泽。
泽泽接到了这个任务，就去测量了这个街道上的所有建筑物的高度。
请根据泽泽的数据，计算出最大面积。
思路解析
答案矩形的高度一定是某个建筑的高度。
用单调栈求出左右两侧能够到达的宽度即可。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], h, l, ans;
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
h = max(h, a[i]);
}
for (int i = 1; i <= h; i++) {
l = 0;
for (int j = 1; j <= n; j++) {
if (a[j] >= i) {
l++;
} else {
l = 0;
}
ans = max(i * l, ans);
}
}
printf("%d", ans);
return 0;
}