P8251 题解

谨以此题解，纪念我第一次 NOIO TG 前 25\%。

题意

每次向栈中加入一个二元组 (a_i,b_i)，先不断弹出栈顶元素直至栈空或栈顶元素 (a_j,b_j) 直到其满足 a_i \neq a_j 且 b_i<b_j，然后入栈。如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

在 [l,r] 的区间中每对元素依次做如上操作，求有多少个“成功的”二元组。

思路

看到这题，可以尝试打个 15 分的暴力，在此直接给出代码：

#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)。

代码

/* / / / / / / / / /
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 记录