前言：高一的 noip2025 倒闭了，然后原地退役。但是平常还是想稍微开开脑子愉悦一下身心，遂偶尔做题，记录于此。
由于题解是写给自己看的，所以不太建议阅读，如果真的想读，请配合 Gemini 食用。
Luogu P15652. [省选联考 2026] 排列游戏 / perm *2000
注意到 \(\mathop{\text{mex}}\limits_{i\in[l,r]}\{a_i\}=\min\limits_{i\in[0,l)\cup(r,n)}\{a_i\}\)，因此我们相当于只能确定一些前后缀区间并的 \(\min\)，因此只要确定出这些那么就一定够我们构造一个合法的排列了。
由于我们只能问前后缀，所以不妨问出所有前、后缀 \(\min\)。由于问到 \(0\) 之后后面询问的结果都是 \(0\)，因此可以问前缀问到 \(0\) 后停止，然后直接从后缀开始问到 \(0\) 分界后的位置。这样最坏的询问的次数就是 \(n\)。
确定出前、后缀 \(\min\) 后，考虑填剩下的数。我们一定确定的数排列起来，大小关系形如 \(x_1>x_2>\cdots>x_p>0<y_q<\cdots<y_2<y_1\) 的谷形，因此数字越大、限制越松。因此我们可以考虑从 \(0\) 开始向两端从小到大填数，先填限制紧的，即最开始先填 \(\min(x_p,y_q)\) 对应的区间，然后向两端扩展，以此类推。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#include "perm.h"
#define N 30005
#define ll long long
#define mod
using namespace std;// void init(int,int);
// vector<int>perm(int);
int query(int,int);int n,a[N],pre[N],nxt[N];
bool fl[N];
struct node{int l,r,d;
};
bool operator<(node x,node y){return max(a[x.l],a[x.r])>max(a[y.l],a[y.r]);}void init(int c,int t){}vector<int>perm(int n0)
{n=n0;fill(a,a+n,-1);fill(pre,pre+n,-1);fill(nxt,nxt+n,-1);fill(fl,fl+n,0);int p=0,lst=-1;while(p<n-1){int x=query(p+1,n-1);if(!p||lst!=x) a[p]=x,fl[x]=1;if(!x) break;lst=x;p++;}int q=n-1;lst=-1;while(p<q){int x=query(0,q-1);if(!x) break;if(!q||lst!=x) a[q]=x,fl[x]=1;lst=x;q--;}for(int i=0;i<n;i++){if(a[i]) continue;goto lab;}a[n-1]=0;fl[0]=1;lab:;// for(int i=0;i<n;i++) cerr<<a[i]<<' ';cerr<<'\n';lst=0;for(int i=0;i<n;i++){if(a[i]<0) continue;lst=i;break;}for(int i=1;i<n;i++){if(a[i]<0) continue;pre[i]=lst;nxt[lst]=i;lst=i;}priority_queue<node>que;for(int i=0;i<n;i++){if(a[i]) continue;que.push({pre[i],i,0});que.push({i,nxt[i],1});}int num=0;while(!que.empty()){auto [l,r,d]=que.top();que.pop();// cerr<<"["<<l<<','<<r<<"] "<<d<<'\n';for(int i=l+1;i<r;i++){while(fl[num]) num++;a[i]=num;fl[num]=1;}if(!d&&l>0) que.push({pre[l],l,0});//,cerr<<"ins ["<<pre[l]<<','<<l<<"]\n";else if(d&&~r&&r<n-1) que.push({r,nxt[r],1});//,cerr<<"ins ["<<r<<','<<nxt[r]<<"]\n";// for(int i=0;i<n;i++) cerr<<a[i]<<' ';cerr<<'\n';}vector<int>res;for(int i=0;i<n;i++) res.push_back(a[i]);return res;
}
Luogu P10767. 「CROI · R2」在相思树下 II *2200
dp，设当前节点为 \(i\)，左、右儿子为 \(x,y\)。
那么设 \(l_i,r_i\) 分别表示能够在 \(i\) 号节点获胜的选手至少有多少个比这个节点获胜的值 \(d\) 小/大。
这句话有点绕，但是我不太会表述，洛谷题解也全都是一坨，建议配合 Gemini 食用。
考虑这一轮为 \(\max\) 的情况。对于下界，由于都比 \(d\) 小，所以易得 \(l_i=l_x+l_y+1\)；对于上界，只有胜出的是可以被计入的，最坏情况即 \(r_i=\min(r_x,r_y)+1\)。\(\min\) 的情况同理。
于是某一层的范围就是这一层所有的节点上、下界的最小值。设第 \(i\) 层下、上界为 \(f_i,g_i\) 的话，那么询问即要求 \(a\in(f_b,2^n-g_b+1)\)。
时间复杂度 \(O(2^n+m)\)。
#include<bits/stdc++.h>
#define N 1000005
#define M 25
#define ll long long
#define lc (i<<1)
#define rc (i<<1|1)
#define mid (l+r>>1)
#define mod
using namespace std;int n,m,a[N<<1],fl[N<<1],fr[N<<1],f[M],g[M];void dp(int i,int l,int r)
{if(l>=r) return;int j=log2(r-l+1);dp(lc,l,mid);dp(rc,mid+1,r);if(a[i]==1){fl[i]=fl[lc]+fl[rc]+1;fr[i]=min(fr[lc],fr[rc]);}else{fl[i]=min(fl[lc],fl[rc]);fr[i]=fr[lc]+fr[rc]+1;}f[j]=min(f[j],fl[i]);g[j]=min(g[j],fr[i]);
}int main()
{//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<(1<<n);i++) cin>>a[i];fill(f+1,f+n+1,1e9);fill(g+1,g+n+1,1e9);dp(1,1,1<<n);while(m--){int x,y;cin>>x>>y;y--;cout<<(f[y]<x&&g[y]+x-1<(1<<n)?"Yes":"No")<<'\n';}return 0;
}