题解：P17197 [KOI 2026 #2] 删除局部最小值
lailai0916
·
·
题解
题意简述
每轮同时删除当前序列中所有非端点的局部最小值。
每次询问给出一个子数组和轮数 t，
求执行 t 轮后剩余的元素数量。
解题思路
对原排列建立大根笛卡尔树。
它的中序遍历顺序与原下标相同，
每个父节点的值都大于孩子。
考虑当前序列中的一个非端点元素。
若对应节点没有孩子，
其中序前驱和后继都只能是祖先，值均大于它，
所以该元素是局部最小值。
若节点存在左孩子，左侧相邻元素位于左子树中，
其值小于当前节点；存在右孩子时同理。
因此节点有孩子就不可能是局部最小值。
所以一轮变换等价于删除除序列两端外的所有叶子。
删除叶子后，中序顺序与堆性质仍然成立，
剩余树仍是剩余序列的大根笛卡尔树。
定义节点 u 的子树高度 h_u。
叶子高度为 1，其他节点的高度为孩子最大高度加一。
若一棵完整子树不包含序列端点，
它会从叶子开始逐层删除，
节点 u 恰好在第 h_u 轮被删除。
考虑询问区间 [l,r]。
区间笛卡尔树中，从根到 l 与从根到 r 的两条链永远保留。
链上节点始终连接着通往某个区间端点的方向，
不会成为需要删除的非端点叶子。
链外的每个连通部分则是原笛卡尔树中的一棵完整子树。
记原树中节点 u 的子树下标区间为 [L_u,R_u]。
笛卡尔树子树的中序下标连续。
一个位于 [l,r] 内的节点在端点链上，
当且仅当它的子树包含 l 或 r。
因此，节点 u 会在询问的前 t 轮内被删除，
当且仅当：
L_u>l\land R_u<r\land h_u\leq t
两个严格不等式表示整棵子树都位于询问内部，
高度条件表示该节点的删除轮次不超过 t。
询问答案等于初始长度减去满足条件的节点数。
问题变成静态三维偏序计数。
节点对应点 (L_u,R_u,h_u)，
询问要求统计 L_u>l、R_u\leq r-1、h_u\leq t。
先把节点按 L_u 从大到小排序，
把询问按 l 从大到小排序。
扫描询问时，将所有满足 L_u>l 的节点加入数据结构。
剩下只需在线统计二维前缀：
R_u\leq r-1\land h_u\leq t
使用树状数组套树状数组维护这个二维前缀。
外层下标是 R_u。
对每个节点 (R_u,h_u)，
先把 h_u 加入外层更新路径
所有高度收集完毕后，分别排序去重并建立内层树状数组。
激活一个节点时，
沿同一条外层更新路径在对应内层高度位置加一。
查询 $(r-1,t)$ 时，
沿外层前缀查询路径累加内层不超过 $t$ 的数量，
恰好得到两个剩余不等式同时成立的节点数。
笛卡尔树用单调栈在线性时间建立。
再用一次非递归后序遍历计算 $L_u,R_u,h_u$，
避免深度为 $O(n)$ 时递归栈溢出。
建树与子树信息预处理为 $O(n)$。
二维树状数组的建立、更新和查询总时间复杂度为
$O((n+q)\log^2 n)$，空间复杂度为 $O(n\log n+q)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int n,q;
int a[N],st[N],ls[N],rs[N],lb[N],rb[N],h[N],seq[N],ord[N],ans[N];
vector<int> val[N];
vector<int> tr[N];
struct query
{
int l,r,t,id;
};
query qry[N];
void add(int x,int y)
{
for(int i=x;i<=n;i+=i&-i)
{
int p=lower_bound(val[i].begin(),val[i].end(),y)-val[i].begin()+1;
int siz=tr[i].size();
for(int j=p;j<siz;j+=j&-j)tr[i][j]++;
}
}
int ask(int x,int y)
{
int res=0;
for(int i=x;i;i-=i&-i)
{
int p=upper_bound(val[i].begin(),val[i].end(),y)-val[i].begin();
for(int j=p;j;j-=j&-j)res+=tr[i][j];
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
int top=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int last=0;
while(top&&a[st[top]]<a[i])last=st[top--];
if(top)rs[st[top]]=i;
if(last)ls[i]=last;
st[++top]=i;
}
int cnt=1;
seq[1]=st[1];
for(int i=1;i<=cnt;i++)
{
int u=seq[i];
if(ls[u])seq[++cnt]=ls[u];
if(rs[u])seq[++cnt]=rs[u];
}
for(int i=n;i>=1;i--)
{
int u=seq[i];
lb[u]=ls[u]?lb[ls[u]]:u;
rb[u]=rs[u]?rb[rs[u]]:u;
h[u]=max(h[ls[u]],h[rs[u]])+1;
}
for(int i=1;i<=n;i++)
{
for(int j=rb[i];j<=n;j+=j&-j)val[j].push_back(h[i]);
}
for(int i=1;i<=n;i++)
{
sort(val[i].begin(),val[i].end());
val[i].erase(unique(val[i].begin(),val[i].end()),val[i].end());
tr[i].resize(val[i].size()+1);
ord[i]=i;
}
for(int i=1;i<=q;i++)
{
cin>>qry[i].l>>qry[i].r>>qry[i].t;
qry[i].id=i;
ans[i]=qry[i].r-qry[i].l+1;
}
sort(ord+1,ord+n+1,[](int x,int y)
{
return lb[x]>lb[y];
});
sort(qry+1,qry+q+1,[](const query &x,const query &y)
{
return x.l>y.l;
});
int pos=1;
for(int i=1;i<=q;i++)
{
while(pos<=n&&lb[ord[pos]]>qry[i].l)
{
int u=ord[pos++];
add(rb[u],h[u]);
}
ans[qry[i].id]-=ask(qry[i].r-1,qry[i].t);
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
return 0;
}
```