https://ac.nowcoder.com/acm/contest/38630/F
https://leetcode.cn/problems/count-ways-to-build-rooms-in-an-ant-colony/submissions/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5+10,mod=1e9+7;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;

int fact[N],infact[N];
vector<int> g[N];
int fa[N];
int n;
int sz[N],f[N];
int qmi(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
void dfs(int u){
    f[u]=sz[u]=1;
    for(auto v:g[u]){
        dfs(v);
        f[u]=1ll*f[u]*f[v]%mod*infact[sz[v]]%mod;
        sz[u]+=sz[v];
    }
    f[u]=1ll*f[u]*fact[sz[u]-1]%mod;
}
int solve(int n)
{
    for(int i=1;i<=n;i++) g[i].clear();
    for(int i=2;i<=n;i++){
        cin>>fa[i];g[fa[i]].push_back(i);
    }
    dfs(1);
    return f[1];
}
signed main(){
    fact[0]=1;infact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=fact[i-1]*i%mod;
        infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    int ans=1;
    cin>>n;
    int tot=0;
    for(int i=1;i<=n;i++){
        int c;cin>>c;
        tot+=c;
        ans=infact[c]*ans%mod*solve(c)%mod;
    }
    cout<<ans*fact[tot]%mod;
}

https://leetcode.cn/problems/minimum-number-of-operations-to-make-string-sorted/
class Solution {
public:
    int minimumVisitedCells(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), mn;
        vector<vector<pair<int, int>>> col_st(n); // 每列的单调栈
        for (int i = m - 1; i >= 0; --i) {
            vector<pair<int, int>> st; // 当前行的单调栈
            for (int j = n - 1; j >= 0; --j) {
                auto &st2 = col_st[j];
                mn = INT_MAX;
                if (i == m - 1 && j == n - 1) // 特殊情况：已经是终点
                    mn = 0;
                else if (int g = grid[i][j]; g) {
                    // 在单调栈上二分
                    auto it = lower_bound(st.begin(), st.end(), j + g, [](const auto &a, const int b) {
                        return a.second > b;
                    });
                    if (it < st.end()) mn = min(mn, it->first);
                    it = lower_bound(st2.begin(), st2.end(), i + g, [](const auto &a, const int b) {
                        return a.second > b;
                    });
                    if (it < st2.end()) mn = min(mn, it->first);
                }
                if (mn == INT_MAX) continue;

                ++mn; // 加上 (i,j) 这个格子
                // 插入单调栈
                while (!st.empty() && mn <= st.back().first)
                    st.pop_back();
                st.emplace_back(mn, j);
                while (!st2.empty() && mn <= st2.back().first)
                    st2.pop_back();
                st2.emplace_back(mn, i);
            }
        }
        return mn < INT_MAX ? mn : -1;
    }
};