注意：本题解及其时间相近的题解是 Yurchiu 退役之前最晚的题解。本题解是 Yurchiu 退役之前写的最后一个题解。其中若语言、排版有不合适的地方，或者有错误，请 dalao 轻喷。

“丹钓战”，顾名思义，就是单调栈。~~所以本题用到了单调栈。~~

题意

有 $n$ 个二元组 $(a_i, b_i)$ ，编号为 $1$ 到 $n$ 。
有一个初始为空的栈 $S$ ，向其中加入元素 $(a_i, b_i)$ 时，先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j , b_j)$ 满足 $a_i \neq a_j$ 且 $b_i < b_j$ ，然后再将其加入栈中。
如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。
有 $q$ 个询问 $[l_i, r_i]$ ，询问若将编号在 $[l_i, r_i]$ 中的二元组按编号从小到大依次入栈，“成功的”二元组数目。询问之间相互独立。
对于所有测试点： $1 \leq n, q \leq 5 \times 10^5$ ， $1 \leq a_i, b_i \leq n$ ， $1 \leq l_i \leq r_i \leq n$ 。

点击查看题解

题解 - 简略版

提供一个在线的时间复杂度为 $\mathcal{O}(n\log n+q)$ 的算法。

下面提到的“栈”指题面中的“栈”。令所有元素依次入栈，设当第 $i$ 号二元组入栈时，栈内元素数量为 $a_i$ 。按编号顺序，所有的 $a_i$ 形成了一个数列 $A$ 。

那么对于任意一个询问区间 $[l,r]$ ，假如第 $x$ 号二元组是“成功的”，那么 $a_x$ 满足：

\large a_x\le\min_{i=l_j}^{x}(a_i)

我们称这样的 $a_x$ 是“成功的”，那么，对于这个区间，所有“成功的” $a_x$ 按编号顺序将会排列成一个单调不升序列 $S_{l,r}$ ，这个区间的答案就是 $|S_{l,r}|$ 。

在 $S$ 中，第 $i$ 个数 $b_{i}$ 和数 $b_{i+1}$ 必定满足：假设 $b_i$ 对应 $A$ 中的 $a_p$ ， $b_{i+1}$ 对应 $a_q$ ，那么 $a_p$ 后面第一个小于等于 $a_p$ 的数是 $a_q$ 。我们称 $a_p$ 的 next 是 $a_q$ 。所有 $a_i$ 的 next 可以通过单调栈求得。

注：这个求 next 的模板题，可以在 luogu 上搜单调栈。~~next 这个名字是我自己起的~~。

设 $f(i,j)=|S_{i,j}|$ 。如果所有 $a_i$ 向它的 next 连边，这样会构造出一个森林。以所有没有 next 的 $a_x$ 为根节点（设其深度为 $1$ ），那么 $a_i$ 的深度就是 $f(i,n)$ 的值。

如果 $a_j\in S_{i,n}$ （ $j\ge i$ ），那么必有：

f(i,j)=f(i,n)-f(j,n)+1

设 $a_w\in S_{i,j}$ 是 $S_{i,j}$ 中的最小值（若有多个最小值，规定最靠近 $j$ 的为最小值），那么必有：

f(i,j)=f(i,w)=f(i,n)-f(w,n)+1

用 ST 表维护区间最小值即可。

~~简略版比详细版好。~~

详细版

题解 - 详细版

提供一个时间复杂度为 $\mathcal{O}(n\log n+q)$ 的算法，大致是把问题转化为静态 RMQ 问题，利用 ST 表解决。其瓶颈也在于此。

拿到这个题，我先打暴力，也就是按照题意模拟。

之后，我发现如果令所有元素依次入栈，则所询问的区间 $[l,r]$ 内的二元组入栈显然是依次且连续的；在区间 $[l,r]$ 内元素依次入栈时，不会有区间后面（即编号大于 $r$ ）的二元组压入，可能会有在区间前面（即编号小于 $l$ ）的一些二元组弹出。

下面所提的“栈”，均指从 $1$ 到 $n$ 进行整个过程的栈。

所以我想，接下来应当研究如何根据每个过程栈的某些信息，来降低得到区间 $[l,r]$ 的答案的时间复杂度。

如何判定二元组是否是“成功的”呢？

首先看“成功”的定义：如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

对于一次询问 $[l,r]$ ，显然，第 $l$ 号二元组一定是“成功的”。如果我们说栈的大小指栈中元素的数量，那么按照“成功”的定义，如果接下来的第 $l+1$ 号二元组压入后，栈的大小不大于压入 $l$ 时栈的大小（因为可能会有一些二元组被弹出），那么它也是“成功的”。

当第 $i$ 个二元组压入后，如果此时栈的大小不大于 $[l,i-1]$ 区间上各元素压入时栈的大小的最小值（这样才能保证符合题意，即当时确实是只有 $i$ 这一个二元组），那么它才是“成功的”。显然这些“成功的”二元组对应的栈的大小形成了一条单调不升序列，这个序列的长度即为答案。

通过对判定二元组“成功”的研究，我们可以发现不在 $[l,r]$ 内的二元组，对于判断 $[l,r]$ 中二元组的“成功”与否，是没有影响的。

那么我们可以转化问题了。

设 $a_i$ 表示压入第 $i$ 个二元组时，栈的大小（显然可以 $\mathcal{O}(n)$ 得到所有的 $a_i$ ）。那么问题转化为：

给定数列 $a$ ，及 $q$ 组询问，每次询问给定的 $[l,r]$ 区间上以 $l$ 开头的一条单调不升序列的长度。

为了方便，我把这个特殊的单调不升序列称为（ $[l,r]$ 区间上的）S 序列。这是个怎样的序列呢？这个 S 序列有这样的性质——“可减性”。

设 $f(i,j)$ 表示 $[i,j]$ （ $j\ge i$ ）区间上的 S 序列的长度；特殊地， $f(i)$ 表示 $[i,n]$ 区间上 S 序列的长度。如果 $a_j$ 在 $[i,n]$ 的 S 序列上，那么必有：

f(i)-f(j)+1=f(i,j)

这个结论是显然的。由于二元组入栈依次且连续，这就决定 S 序列上连续的两个数 $p,q$ （ $p\ge q$ ），在原数列上必定满足： $q$ 是 $p$ 之后第一个小于等于 $p$ 的数。为了方便，把 $q$ 称为 $p$ 的 next。显然一个数的 next 最多只有一个，所以 $[j,n]$ 上的 S 序列必定是 $[i,n]$ 上的 S 序列的末尾。因此就有了这个结论。

那么如何求得 $f(i)$ 呢？

我们可以通过~~丹钓战~~单调栈以 $\mathcal{O}(n)$ 来找到所有 $a_i$ 的 next。单调栈维护自栈底到栈顶单调递增的序列，其中的元素是数字。如果待压入元素小于等于栈顶，则显然此时栈顶的 next 就是待压入元素，弹出栈顶，直至待压入元素大于栈顶或栈为空。正确性显然。

如果所有 $a_i$ 的 next 向 $a_i$ 连边，显然就形成了一个树形结构，即森林（每个节点出度可大于 $1$ ，入度最大为 $1$ ）。以入度为 $0$ 的 $a_i$ 为根节点， $i$ 的深度即为 $f(i)$ 的值。

现在关键是如何得到 $f(l,r)$ 也就是答案。

这里引入一个显然的结论：设 $x$ 是区间 $[l,r]$ 上的最小值，则 $x$ 一定包含在 S 序列中。假设 $x$ 不在 S 序列中，且不是第 $l$ 个数（如果是第 $l$ 个数，那么显然它是 S 序列的开头，因为第 $l$ 号二元组一定是“成功的”），则 $x$ 前面必有一个数 $y$ 在 S 序列里面。既然 $x$ 和 $y$ 之间的数没有在 S 序列里面，则必定它们之间的数比 $y$ 大。那么显然 $x$ 就成为了 $y$ 的 next，和假设矛盾。

显然，区间中，值为 $x$ 的数必定是这个区间中 S 序列中的最后一个数（这里的 $x$ 同上段文字）。设这个区间最后一个值为 $x$ 的数的位置是 $w$ ，则区间 $[l,r]$ 的答案显然是：

f(l,r)=f(l,w)=f(l)-f(w)+1

如何得知这个 $w$ 呢？

显然，这已经是一个静态 RMQ 问题了。

定义二元组 $(a_i,i)$ 的大小关系为： $(a_i,i)<(a_j,j)$ 当且仅当 $a_i<a_j$ ，或 $a_i=a_j$ 时 $i>j$ 。使用能维护区间最值的数据结构（静态即可，例如 ST 表）维护 $[1,n]$ 的二元组即可。这样定义大小关系，就能保证维护的确实是一个区间的 $w$ 。

时间复杂度： $\mathcal{O}(n\log n+q)$ 。 $\mathcal{O}(n\log n)$ 的预处理， $\mathcal{O}(1)$ 的查询。

使用线段树，时间复杂度则为： $\mathcal{O}(n+q\log n)$ 。 $\mathcal{O}(n)$ 的预处理， $\mathcal{O}(\log n)$ 的查询。

上文未明确的细节见代码。代码如下，欢迎 hack！若题解有疏漏或错误之处，也可指出！

代码

num[]： $A$ 数列。
f[]： $f(i,n)$ 。

#include<bits/stdc++.h>
using namespace std;
namespace _
{
    typedef int ll;
    const ll N=500000+10,inf=2147483640,V=19;
    struct P{ll a,b;}p[N],stk[N],st[V+5][N];
    struct edge{ll nxt,to;}e[N];
    ll n,q,head[N],cnt=0,num[N],f[N],top=0,b[N];
    inline ll read()
    {
        ll s=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')
                w=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
            s=s*10+ch-'0',ch=getchar();
        return s*w;
    }
    inline void write(ll x)
    {
        if(x>9) 
            write(x/10);
        putchar(x%10+'0');
    }
    P min(P a,P b)//规定大小
    {
        if(a.a<b.a) return a;
        else if(a.a==b.a)
        {
            if(a.b<b.b) return b;
            return a;
        }
        return b;
    }
    void add(ll a,ll b)
    {
        e[++cnt]=(edge){head[a],b};
        head[a]=cnt; 
    }
    void main()
    {
        ll x,y,len;
        n=read(); q=read();
        for(ll i=1;i<=n;i++) p[i].a=read();
        for(ll i=1;i<=n;i++) p[i].b=read();
        for(ll i=1;i<=n;i++)
        {
            while(top>=1&&!(stk[top].a!=p[i].a&&stk[top].b>p[i].b)) top--;
            stk[++top]=p[i]; num[i]=top;//求 A 数列
        }
        
        //构造 ST 表：
        for(int i=1;i<=n;i++)
            st[0][i]=(P){num[i],i};
        for(int i=1;i<=V;i++)
            for(int j=1;j<=n;j++)
                st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        for(int i=1;i<=V;i++)
            b[1<<i]=1;
        for(int i=1;i<=n;i++)
            b[i]+=b[i-1];
        
        top=0;
        for(ll i=1;i<=n;i++)
        {
            while(top>=1&&stk[top].a>=num[i])
                add(i,stk[top].b),top--;
            //求每个 a_i 的 next，连边
            stk[++top]=(P){num[i],i};
        }
        
        //求 f(i,n)
        for(ll i=n;i>=1;i--)
        {
            if(f[i]==0) f[i]=1;
            for(ll j=head[i];j;j=e[j].nxt)
            	f[e[j].to]=f[i]+1;
        }
        
        for(ll i=1;i<=q;i++)
        {
            x=read(); y=read(); len=y-x+1;
            write(f[x]-f[min(st[b[len]][x],st[b[len]][y+1-(1<<b[len])]).b]+1);
            //f(x,y)=f(x,w)=f(x,n)-f(w,n)+1
            putchar('\n');
        }
        return;
    }
}
int main()
{
    _::main();
    return 0;
}