2022 03 06 栈&滑动窗口【未完成】

单调栈	CEOI 2011 – Balloons	提高+	https://www.luogu.com.cn/problem/P4697
单调栈	CEOI 2020 - Fancy Fence	NOI-	https://www.luogu.com.cn/problem/P6801
括号序列	USACO 2017 Open S - Modern Art 2	提高+	https://www.luogu.com.cn/problem/P3668
单调栈	CF gym101102D Rectangles, ACPC2016	提高+	https://codeforces.com/gym/101102/problem/D
单调栈	IOI 2004 - Empodia	NOI-	https://www.luogu.com.cn/problem/P5923

滑动窗口	USACO 2016 Jan P. Fort Moo	提高+	https://www.luogu.com.cn/problem/P3135
扫描线	APIO 2015 - Palembang Bridges	NOI-	https://www.luogu.com.cn/problem/P3644
扫描线	USACO 2019 Feb G. Painting the Barn	NOI-	https://www.luogu.com.cn/problem/P6100
扫描线	APIO 2009 - Digging for Oil	NOI-	https://www.luogu.com.cn/problem/P3625
扫描线	IOI 2005 - Garden	提高+	https://www.spoj.com/problems/IOIGARD/en/

Balloons

有两个关键点：对于 \(i < j < k\)，\(x_i < x_j < x_k\)，那么

1. 对于 \(r_i \le r_j\)，气球 \(i\) 不会对 \(j\) 以后的气球产生影响
2. 对于 \(r_i > r_j\)，若 \(r_k < r_j\)，那么 \(i\) 不会对 \(k\) 产生影响，\(j\) 可能对 \(k\) 产生影响

所以可维护一个单调递减的栈，

1. 取出栈顶 \(j\) 对当前决策点 \(k\) 进行决策；
2. 若 \(r_k < r_j\)，则它不会受前面的气球的影响了。把 \(r_k\) 加入栈顶，退出；
3. 否则弹出栈顶 \(j\)（为了维护 \(r_j\) 递增），回到 1。

时间复杂度：\(O(n)\)

/**
 * @file luogu/4697/main.cpp
 * @brief
 * @see
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 2022/6/23 13:30:37
 **/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 200005;
int n, stk[N], top;
double r[N], x[N];
int main() {
  // High rating and good luck!
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%lf%lf", &x[i], &r[i]);
    while (top) {
      int j = stk[top];
      double limit = (x[i] - x[j]) * (x[i] - x[j]) / (4.0 * r[j]);
      if (r[i] > limit) r[i] = limit;
      if (r[i] <= r[j])
        break;
      else
        --top;
    }
    stk[++top] = i;
    printf("%.6lf\n", r[i]);
  }
  return 0;
}

花式围栏

数这里有多少个矩形。

考虑维护一个高度递增的单调栈。

不妨设

• 当前要加入的矩形为 \(a\) ，高度为 \(h\)
• 单调栈顶部的矩形为 \(x\)，高度为 \(h_1\)，宽为 \(w_1\)
• 单调栈次栈顶矩形为 \(y\)，高度维 \(h_2\)

如果 \(h<h_1\)，\(x\) 高于 \(a\) 的部分不会对后加入的矩形产生影响，将 \(x\) 的高度削到 \(\max(h, h_2)\)

接着考虑削去该矩形对答案的贡献，即求出“四边都落在 \(x\) 内部（包括边界）且至少有一边落在被削去矩形

考虑用单调栈维护高度单调递增的矩形。

现在假如我们需要将第 \(i\) 个矩形插入单调栈中，如果该矩形比栈顶矩形高度更高则直接插入，否则我们需要将高出当前矩形的部分删除，并累加该部分的答案。

假如当前栈顶的矩形宽为 \(w_p\)，高为 \(h_p\)，栈顶下面的矩形宽为 \(w_n\)，高为 \(h_n\)，要插入的矩形宽为 \(w_i\)，高为 \(h_i\)。容易发现，我们需要将栈顶的矩形的高度降至 \(\max(h_n,h_i)\)
才能不破坏单调性。

现在问题变成了如何计算被删除部分的贡献。

容易发现，这部分对答案的贡献为所有两个顶点落在被删除部分，其他两个顶点在被删除部分以外的矩形的个数。由容斥原理可知，答案即为栈顶矩形的子矩形个数，减去删除超高部分后的矩形的子矩形个数。

而根据组合数学知识可知，一个 \(w \times h\) 的矩形，其子矩形个数为 \(\dfrac{w \times (w+1)}{2} \times \dfrac{h \times (h+1)}{2}\)。

/**
 * @file luogu/6801/main.cpp
 * @brief
 * @see https://www.luogu.com.cn/record/77840112
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 2022/6/23 21:25:48
 **/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MOD = 1e9 + 7;
const int N = 100005;
ll h[N], w[N];
stack<int> s;
ll C2(ll x) { return x * (x - 1) / 2 % MOD; }
int main() {
  // High rating and good luck!
  int n;
  ll ans = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];
  for (int i = 1; i <= n; ++i) cin >> w[i];
  s.push(0);
  // 注意终止条件为 n+1，最后推进一个空矩形得到结果
  for (int i = 1; i <= n + 1; ++i) {
    // 考虑第 i 个矩形
    ll sw = 0;
    // 如果这个矩形比栈顶矩形低
    while (h[s.top()] > h[i]) {
      int u = s.top();
      s.pop();
      sw = (sw + w[u]) % MOD;  // 当前超高部分的宽度
      ans = (ans +
             (C2(h[u] + 1) - C2(max(h[i], h[s.top()]) + 1))  // 公式的变形
                 * C2(sw + 1) % MOD +
             MOD) %
            MOD;
    }
    w[i] += sw;  // 加宽矩形 i（保证栈的单调性）
    s.push(i);
  }
  cout << ans << endl;
  return 0;
}

Modern Art 2

给定 \(N\) 中颜色和一张布条，每种颜色只能使用一次；每天可以选取一些颜色对布条染色，每天的染色区间不能相交；后来的每天可以选另外一些颜色继续染色，可以覆盖前些天的染色。给定一条染色结束的布条，问用多少天可以如是复制一份，或者不能复制。

可以看出颜色必须是一层包一层，如 ABCCBA；如果出现 ABAB 的情况则为不可能。

用栈判断：

• 如果下一个字符 \(a\) 和栈顶字符相同，不变；
• 与栈顶字符不同，一直出栈直到栈顶字符与 \(a\) 相同，同时标记出栈的字符；如果栈空了都不同那就是错
• \(a\) 是一个已经出栈的字符就是错

/**
 * @file luogu/3668/main.cpp
 * @brief
 * @see https://www.luogu.com.cn/record/77842375
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 2022/6/24 20:32:32
 **/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 1e5 + 10;
int n, a[N];
int s[N], t[N];  // s 为当前点是哪一个点的开头，t 表示当前点是那一个点的结尾
int x[N], y[N];  // 每种颜色的开始位置和结束位置
int top, ans;
int stk[N];
int main() {
  // High rating and good luck!
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    y[a[i]] = i;                    // 颜色 a[i] 最后出现的位置
    if (x[a[i]] == 0) x[a[i]] = i;  // 颜色 a[i] 最先出现的位置
  }
  for (int i = 1; i <= n; ++i) {
    if (x[i] != 0) s[x[i]] = i;  // s 是颜色 i 的开头
    if (y[i] != 0) t[y[i]] = i;  // t 是颜色 i 的结尾
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i] == 0) {  // 一笔刷下来，颜色中间不能有空白
      if (top != 0) {
        ans = -1;
        break;
      }
    } else {
      if (s[i] != 0) {      // 当前点是一个点的开头
        stk[++top] = s[i];  // 多了一种颜色
        ans = max(ans, top);
      }
      if (stk[top] != a[i]) {  // 出现了颜色交叉的情况
        ans = -1;
        break;
      }
      if (t[i] != 0) {  // 当前点是一个点的结尾
        top--;          // 少了一种颜色
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Rectangles

问一个大的矩阵里面有多少个子矩阵，满足每个子矩阵的每一个元素相等。

//
//Created by just_sort 2016/9/30 15:32
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1002;
int S[maxn][maxn], TOP[maxn][maxn];
int A[maxn],B[maxn],sz,sum;
int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf("%d",&S[i][j]);
            }
        }
        long long ans = 0;
        for(int i = 1; i <= n; i++){
            sz = sum = 0;
            for(int j = 1; j <= m; j++){
                int h = (S[i][j] == S[i-1][j] ? TOP[i-1][j] + 1 : 1);
                int w = 1;
                TOP[i][j] = h;
                if(S[i][j] != S[i][j-1]) sum = sz = 0;
                while(sz && h <= A[sz]){
                    sum -= A[sz] * B[sz];
                    w += B[sz--];
                }
                A[++sz] = h;B[sz] = w;
                sum += A[sz] * B[sz];
                ans += sum;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Empodia

这题可以看出数列是一个\(1\) 到 \(n\) 的全排列，可知满足 empodia 条件的的 \(i, j\) 必然满足

\[ a_j - a_i = j - i \]

转换得到

\[ a_j - j = a_i - i \]

枚举等式中的 \(i, j\) 即可，但时间复杂度 \(O(n^2)\)，不可能。

考虑如下优化：

设 \(f[i]\) 为该点作为最大值能够向左边延伸到的最左位置，\(g[i]\) 为该点作为最小值能向右延伸到的最右位置，这是一个二维偏序。对于点对 \((i, j)\)，\(f[j] \le i\) 且 \(g[j] \ge j\) 即为满足条件。

因为区间之间不存在包含关系，故可维护 \(g[i]\) 的单调栈，取尽可能小的 \(i\)。

Let \(v[0],v[1],\ldots,v[n-1]\) denote the input sequence. An interval \([i \ldots j]\) is framed if all three of the following conditions hold:

1. \(v[i]−i=v[j]−j\)
2. \(v[i]=\min⁡(v[i…j])\)
3. \(v[j]=\max(v[i\ldots j])\)

Our approach will be to iterate over all \(j=[0,n)\) and check whether \(j\) contributes a new empodio with right endpoint \(j\).

• Maintain a stack \(mn\) consisting of all indices \(i\) satisfying the second condition.
• When we increment \(j\), repeatedly pop the top element \(i\) of \(mn\) while \(v[i]>v[j]\). Then push \(j\) into \(mn\).
• To check whether \(j\) is part of an empodio, find the maximum \(i\in mn\) such that \(v[i]-i=v[j]-j\). If \(i\) is to the right of the rightmost left endpoint of any empodio found so far and \(v[j]=\max(v[i\ldots j])\), then we have found a new empodio.

To check whether \(v[j]=\max(v[i\ldots j])\), we can maintain a second stack \(mx\) that stores all indices \(i\) such that \(v[i]=\max(v[i\ldots j])\).

ref: https://usaco.guide/problems/ioi-2004empodia/solution

#include <algorithm>
#include <iostream>

using namespace std;

int n, r;
int A[1100002], C[1100002];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> A[i];
  int i, j;
  for (i = n; i; i--) {
    int mayor = A[i];
    for (j = i + 1; j <= n && A[j] > A[i]; j++) {
      mayor = max(A[j], mayor);
      if (A[j] == A[i] + j - i && A[j] == mayor) {
        r++;
        C[i] = j;
        break;
      }
      if (C[j]) break;
    }
  }
  cout << r << "\n";
  for (i = 1; i <= n; i++)
    if (C[i]) cout << i << " " << C[i] << "\n";
  return 0;
}