本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-02 10:23:02

前言：

15+30+10=55pts，没进入前 25%，我是垃圾

T1-Stack

题目解法：

对于每一个成功的二元组，把它称为关键点（套用官方题解原话）。
然后观察一下可以发现，对于每一个二元组，都有一个区间 $[l,r]$，使其在这个区间中是关键点。可以对于每一个二元组，把最小的，满足其在区间 $[l,r]$ 中是关键点的 $l$ 求出来，记为 $p_i$。而它的 $r$ 是多少都可行，就记为 $n$。这样最后询问时，答案就是询问区间 $[l,r]$ 中满足 $\forall{i} \in [l,r],p_i \le l$ 的数量。
显然，$p$ 数组可以 $O(n)$ 预处理。
然后，从 $1$ 到 $n$ 枚举端点，依次将 $p_i$ 加入树状数组。如果当前点是某一组询问的左端点，当前点为 $i$，记当前小于等于 $i$ 的点的数量为 $sum(i)$，那么这组询问的答案减去 $sum(i)$，因为最后要求的是 $[l,r]$ 这个区间，所以先把 $sum(i)$（也就是区间 $[1,l-1]$ 的答案）减去。如果当前点是某一组询问的右端点，记这组询问的左端点为 $left$，当前小于等于 $left$ 的点的数量为 $sum(left)$，这组询问的答案加上 $sum(left)$（就是区间 $[1,r]$ 的答案），因为区间 $[1,l-1]$ 的答案已经提前减去了，所以现在的答案就是区间 $[l,r]$ 的答案。

注意：

1. 一定要枚举到第 $i$ 个顶点时才把 $p_i$ 加入树状数组，不然会导致错误的统计了 $i+1$ 往后的顶点的答案。
2. 一定要先删除多余的答案之后再把 $p_i$ 加入树状数组，不然会错误的减去 $p_i$对答案的贡献。

$\color{green}\text{AC 代码：}$

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-');
        if(x>=10)
            write(x\/10);
        putchar(x%10^48);
    }
    const int maxn=5e5+5;
    int n,q;
    int a[maxn];
    int b[maxn];
    int p[maxn];
    int sta[maxn];
    int top;
    int tre[maxn<<2];
    vector<int> left[maxn];
    vector<int> right[maxn];
    int given_l[maxn];\/\/每组询问的l
    int ans[maxn];
    inline int lowbit(int x)
    {
        return x&-x;
    }
    inline void add(int x,int val)
    {
        while(x<=n)
        {
            tre[x]+=val;
            x+=lowbit(x);
        }
    }
    inline int sum(int x)
    {
        int res=0;
        while(x>0)
        {
            res+=tre[x];
            x-=lowbit(x);
        }
        return res;
    }
    int main()
    {
        n=read();
        q=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            p[i]=1;
        }
        for(int i=n;i>=1;i--)
        {
            while((b[i]>b[sta[top]]&&(a[i]!=a[sta[top]]))&&top)
            {
                p[sta[top]]=i+1;
                top--;
            }
            sta[++top]=i;
        }
        int li,ri;
        for(int i=1;i<=q;i++)
        {
            li=read();
            ri=read();
            left[li].emplace_back(i);
            right[ri].emplace_back(i);
            given_l[i]=li;
        }
        for(int i=1;i<=n;i++)
        {\/\/枚举端点
            for(int j=0;j<left[i].size();j++)
            {
                ans[left[i][j]]-=sum(i);
            }
            add(p[i],1);
            for(int j=0;j<right[i].size();j++)
            {
                ans[right[i][j]]+=sum(given_l[right[i][j]]);
            }
        }
        for(int i=1;i<=q;i++)
        {
            write(ans[i]);
            putchar('\n');
        }
        #ifndef ONLINE_JUDGE
        system("pause");
        #endif
        return 0;
    }
}
int main()
{
    Main::main();
    return 0;
}

T2 -Discuss

咕咕咕

T3 -Sort

咕咕咕