思路讲解

https://chatgpt.com/c/689c99ac-b064-8324-881c-c407b94bd235

G-Permutation 题目极简笔记（Notion 块级公式版）

1. 问题核心

操作：两端删除元素，或查询当前最小值并把它追加到 a。
共执行 n 步，问不同的 a 序列数量。
输入保证为排列（每个 1…n 恰好一次）。

2. 关键性质

最小值“时代”严格递增（因为是排列，无重复）。
按“最后一个时代所属的区间”分类：

不重：每个 a 只有一个最后时代；
不漏：每个 a 都有最后时代。

分类后只需两个量：

m：到达最后时代时的区间长度（剩余元素数）；
d：经历的时代个数（最小值更新次数 + 1）。

3. 计数模型（每个时代的 Query 次数）

下面是 q 的约束（最后一个时代至少查询一次；总查询次数不超过 m）：
$q_d \ge 1,\quad q_1,\dots,q_{d-1} \ge 0,\quad \sum_{i=1}^{d} q_i \le m$

固定总查询次数 Q 的分配方案数（隔板法）为：
$\binom{Q + d - 2}{d - 1}$

4. 求和得到闭式

对所有可行的 Q（从 1 到 m）求和，有：

\sum_{Q=1}^{m} \binom{Q + d - 2}{d - 1} = \binom{m + d - 1}{d}

因此，某个区间作为“最后时代”的贡献为：

\binom{m + d - 1}{d}

5. 最终答案

把所有区间（作为最后时代）累加，再加 1（空序列）：

\mathrm{Ans} = \sum_{\text{all intervals}} \binom{m + d - 1}{d} + 1

6. 实现要点（思路提要）

用 RMQ/ST 或单调栈 + 分治，拿到每个“最后时代”区间的 m 与 d；
对每个区间加上上面的组合数；最后整体再加 1。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78844877

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <cstdio>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
namespace Comb{    // 组合数加逆元，依赖于这个MAXN（初始化）
    vector<ll> frac,infrac;
    int ln=1;
    bool initialized=false;
    inline ll binpow(ll a, ll k) {
        ll res = 1;
        a %= mod;
        while (k > 0) {
            if (k & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            k >>= 1;
        }
        return res;
    }

    void Comb(int n) {
        ln = n;
        frac.assign(n + 5, 1);
        infrac.assign(n + 5, 1);
        for (int i = 1; i <= ln; ++i) {
            frac[i] = (frac[i - 1] * i) % mod;
        }
        infrac[ln] = binpow(frac[ln], mod - 2);
        for (int i = ln - 1; i >= 0; --i) {
            infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
        }
    }

    inline ll CC(ll n, ll k) {
        if (k < 0 || k > n) {
            return 0; // Return 0 if k is out of range [0, n]
        }
        if(!initialized){
            Comb(MAXN);
            initialized=true;
        }
        ll res = frac[n];
        res = (res * infrac[n - k]) % mod;
        res = (res * infrac[k]) % mod;
        return res;
    }

    inline ll PP(ll n, ll k) {
        if (k < 0 || k > n) {
            return 0;
        }
        if(!initialized){
            Comb(MAXN);
            initialized=true;
        }
        ll res = frac[n] * infrac[n - k];
        res %= mod;
        return res;
    }
}
using namespace Comb;
// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// https://www.luogu.com.cn/record/230330447 科学计数法小数，小数
namespace QuickRead { // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T> void Cin(T &a) {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc()) {
            if (c == '-') f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc()) {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    void getc(char &a){
        char c=getc();
        while (isspace(c)) {
            c=getc();
        }
        a=c;
    }
    template <typename T> void Cinf(T &a) { // 新增：读取浮点数，支持科学计数法
        T ans = 0;
        bool f = 0; // 负号
        char c = getc();
        // 跳过非数字和小数点前的空白/符号
        while ((c < '0' || c > '9') && c != '.') {
            if (c == '-') f = 1;
            c = getc();
        }
        // 读取整数部分
        while (c >= '0' && c <= '9') {
            ans = ans * 10 + (c - '0');
            c = getc();
        }
        // 如果有小数点，读取小数部分
        if (c == '.') {
            c = getc();
            T frac = static_cast<T>(1);
            while (c >= '0' && c <= '9') {
                frac /= 10;
                ans += (c - '0') * frac;
                c = getc();
            }
        }
        a = f ? -ans : ans;
        // 处理科学计数法部分
        if (c == 'E' || c == 'e') {
            c = getc();
            bool exp_neg = false;
            if (c == '+') {
                c = getc();
            } else if (c == '-') {
                exp_neg = true;
                c = getc();
            }
            int exp = 0;
            while (c >= '0' && c <= '9') {
                exp = exp * 10 + (c - '0');
                c = getc();
            }
            T multiplier = pow(10.0, exp_neg ? -exp : exp);
            a *= multiplier;
        }
    }
    template <typename T, typename... Args> void Cin(T &a, Args &...args) {
        Cin(a), Cin(args...);
    }
    template <typename T> void write(T x) { // 注意，这里输出不带换行
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T> void writef(T x) { // 新增：输出浮点数，默认输出6位小数，支持四舍五入
        if (x < 0) putchar('-'), x = -x;
        using ll = long long;
        int prec = 6; // 默认精度6，可根据需要调整
        // 添加圆整因子
        T round_add = static_cast<T>(5);
        for (int i = 0; i < prec + 1; ++i) {
            round_add /= 10;
        }
        x += round_add;
        ll int_part = static_cast<ll>(x);
        write(int_part); // 输出整数部分
        putchar('.');
        T frac_part = x - int_part;
        for (int i = 0; i < prec; ++i) {
            frac_part *= 10;
            int digit = static_cast<int>(frac_part);
            putchar(digit + '0');
            frac_part -= digit;
        }
    }
} // namespace QuickRead

using namespace QuickRead;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    Cin(lT);
    while(lT--)
        __();
    return 0;
}
/*

*/
// by Gospel_rock znzryb
// 参考了（抄了）OIwiki
// https://www.luogu.com.cn/record/228807838 ST表模版题（max）
// https://www.luogu.com.cn/record/228809172 打乱了插入顺序，和上面是同一道
struct RMQ{
    using ll = long long;
    ll n;vector<ll> tr;bool ismax;vector<ll> origin;
    inline ll lowbit(const ll &x){
        return x&-x;
    }
    private:
    ll get(const ll &a,const ll &b){
        if(ismax){
            return max(a,b);
        }else{
            return min(a,b);
        }
    }
    ll set(){
        if(ismax) return -INF;
        else return INF;
    }
    public:
    RMQ(ll n,bool ismax=true){
        this->n=n;this->ismax=ismax;
        if(ismax) tr.resize(n+5,-INF),origin.resize(n+5);
        else tr.resize(n+5,INF),origin.resize(n+5);
    }
    ll query(ll l,ll r){
        ll res=set();
        while (r>=l) {
            res=get(origin[r],res);
            r--;
            for(;r-lowbit(r)>=l;r-=lowbit(r)){
                res=get(res, tr[r]);
            }
        }
        return res;
    }
    void upd(ll p,ll x){    
        origin[p]=x;
        for(int i=p;i<=n;i+=lowbit(i)){
            tr[i]=origin[i];
            for(int j=1;j<lowbit(i);j<<=1){
                tr[i]=get(tr[i],tr[i-j]);
            }
        }
    }
    ll findpos(ll st=1,ll ed=-1){   // 找到第一个最小值位置，st是开始位置，ed是结束
        ed=ed==-1?n:ed;
        ll l=st,r=ed;
        ll mn=query(st, ed);
        auto check=[&](ll mid){
            if(query(st,mid)==mn){
                return true;
            }
            return false;
        };
        while (l<r) {
            ll mid=l+r>>1;
            if(check(mid)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return l;
    }
};

inline void __(){
    Cin(N);
    RMQ tr(N,false);
    vll A(N+5);
    vll Pos(N+5);
    FOR(i,1,N){
        Cin(A[i]);
        tr.upd(i,A[i]);
        Pos[A[i]]=i;
    }
    ll ans=1;
    function<void (ll,ll,ll)> dfs=[&](ll l,ll r,ll dep){
        if(l>r) return;
        // ll pos=tr.findpos(l,r);
        ll pos=Pos[tr.query(l, r)];
        ll len=r-l+1;
        // q1+q2+qdep+1=len
        ans+=CC(len+dep+1-1,dep+1);
        ans%=mod;
        dfs(l,pos-1,dep+1);
        dfs(pos+1,r,dep+1);
    };
    dfs(1,N,0);
    write(ans);
    putchar('\n');
}
/*
1
2
1 2
AC
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78844877
*/

上面这段代码非常好，下面仅仅只是为了测试一下zkw线段树的这个功能以及常数

源代码

Znzryb's Blog

影石Insta360杯-2025牛客暑期多校训练营9——G.Permutation