P8251 题解
Jerrlee✅
2022-04-01 10:50:31
谨以此题解，纪念我第一次 NOIO TG 前 $25\%$。
## 题意
每次向栈中加入一个二元组 $(a_i,b_i)$，先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j,b_j)$ 直到其满足 $a_i \neq a_j$ 且 $b_i<b_j$，然后入栈。如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。
在 $[l,r]$ 的区间中每对元素依次做如上操作，求有多少个“成功的”二元组。
## 思路
看到这题，可以尝试打个 $15$ 分的暴力，在此直接给出代码：
```cpp
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
#define int long long
pair<int,int> a[500010];
#define fi first
#define se second
signed main(){
//freopen("stack.in","r",stdin);
//freopen("stack.out","w",stdout);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i].fi;
for(int i=1;i<=n;i++) cin>>a[i].se;
while(q--){
stack<int> s,s1;
int x,y,ans=0;
cin>>x>>y;
for(int i=x;i<=y;i++){
int tmp=a[i].fi,temp=a[i].se;
if(s.empty()){
s.push(tmp);
s1.push(temp);
ans++;
}
else{
be:;
if(s.empty()){
s.push(tmp);
s1.push(temp);
ans++;
continue;
}
int xx=s.top(),yy=s1.top();
if(xx!=tmp&&yy>temp){
s.push(tmp);
s1.push(temp);
if(s.size()==1) ans++;
}
else{
s.pop();
s1.pop();
goto be;
}
}
}
cout<<ans<<endl;
}
}
```
接下来讲正解：
我使用的算法是归并树，其实就是归并排序和线段树的结合体，利用线段树记录归并排序的步骤。
它可以用于计算某区间中比某个数小或大的数有多少个，正好适用本题。建树时递归构造子节点，回溯时构造父节点。
学习归并树可以看此篇文章：<https://www.cnblogs.com/bennettz/p/8342242.html>
为什么本题可以转化成求解某区间比某数小的数的数量呢？
这样想：每个元素可以弹出他前面的若干元素，我们计他可以弹出至 $a[i]$ 号元素。如果求解一个区间 $[l,r]$，那么如果这个区间内的某个元素 $a[i]$ 可以弹出至 $l$ 以下，就肯定可以把栈弹空，所以本题就转化为求解区间 $<l$ 的数的数量了。
在程序最开始先模拟一下题目所说的操作，用栈记录下来，然后直接套模板求解某区间比某数小的数的数量即可。
最开始读入的数据可以用一个 `pair` 记录下来，注意细节，刚开始准备的 `stack` 先将一对 `0,0` 入栈以防出错。
本代码时间复杂度大概为 $O(n \ \log^2 \ n)$。
## 代码
```cpp
/* / / / / / / / / /
written by Jerrlee
算法使用：归并树
/ / / / / / / / / */
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
#define int long long
#define fi first
#define se second
pair<int,int> a[500010];
int c[500010],f[50][500010];
void Build(int de,int l,int r){
if(l==r){
f[de][l]=c[l];
return;
}
int mid=(l+r)>>1;
Build(de+1,l,mid);
Build(de+1,mid+1,r);
for(int i=l,j=mid+1,k=l;i<=mid||j<=r;){
if(j>r) f[de][k++]=f[de+1][i++];
else if(i>mid||f[de+1][i]>f[de+1][j]) f[de][k++]=f[de+1][j++];
else f[de][k++]=f[de+1][i++];
}
}//建树
int calc(int de,int L,int R,int l,int r,int x){
if(L>=l&&R<=r) return lower_bound(f[de]+L,f[de]+R+1,x)-f[de]-L;
int mid=(L+R)>>1,ans=0;
if(mid>=l) ans+=calc(de+1,L,mid,l,r,x);
if(mid<r) ans+=calc(de+1,mid+1,R,l,r,x);
return ans;
}//模板部分
signed main(){
//freopen("stack.in","r",stdin);
//freopen("stack.out","w",stdout);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i].fi;
for(int i=1;i<=n;i++) cin>>a[i].se;
stack<pair<int,int> > s,s1;
s.push({0,0});
s1.push({0,0});
for(int i=1;i<=n;i++){
be:
c[i]=s.top().fi;
if(s.size()>1&&!(s.top().se!=a[i].fi&&s1.top().se>a[i].se)){
s.pop();
s1.pop();
goto be;
}
s.push({i,a[i].fi});
s1.push({i,a[i].se});
}//模拟
Build(1,1,n);
while(q--){
int x,y;
cin>>x>>y;
cout<<calc(1,1,n,x,y,x)<<endl;//求出 x-y 区间内数字小于 x 的数量
}
}
```
注：此代码在洛谷只有 $50$ 分，需要加快读（但是我测完 CCF 的官方数据是 $100$）。
快读版：<https://www.luogu.com.cn/paste/1c5p7sdz>
[AC 记录](https://www.luogu.com.cn/record/72805036)