影石Insta360杯-2025牛客暑期多校训练营9——G.Permutation · znzryb
## 思路讲解
[https://chatgpt.com/c/689c99ac-b064-8324-881c-c407b94bd235](https://chatgpt.com/c/689c99ac-b064-8324-881c-c407b94bd235)
# G-Permutation 题目极简笔记（Notion 块级公式版）
## 1. 问题核心
- 操作：两端删除元素，或查询当前最小值并把它追加到 a。
- 共执行 n 步，问不同的 a 序列数量。
- 输入保证为排列（每个 1..n 恰好一次）。
---
## 2. 关键性质
1. 最小值“时代”严格递增（因为是排列，无重复）。
1. 按“最后一个时代所属的区间”分类：
- 不重：每个 a 只有一个最后时代；
- 不漏：每个 a 都有最后时代。
1. 分类后只需两个量：
- 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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78844877)
::: 源代码
```cpp
// 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线段树的这个功能以及常数
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）