L题题解（镜影）

要查询所有的区间，换句话说，你需要检查从1到2，从1到3.从1到4..........总共要查n(n+1)/2次，而n最大是2e5，换句话说，不优化查询方式的话是一定会爆超时的。优化方式我们选择分段查询（st表）st表的知识点我贴在下面：

问题是什么？

给定一个大小为 n 的数组 A ，回答 q 个类型为 [l,r] 的查询，要求回答 min{A[l],A[l+1],…,A[r]} 。

限制条件

1≤n,q≤105
0≤Ai≤109

现有方法（提醒）

每次查询扫描：扫描范围并取最小值。预处理：无，查询： O(n) .
预处理所有数据对：将每一对数据对 (i,j) 的最小值存储在一个表中： O(n2) , 查询： O(1) .
Sqrt-decomposition: 分割成大小为 ≈n−−√ 的块，预处理块的最小值： O(n) , query： O(n−−√) .

关键思路--两幂区块（稀疏表）

为长度为 2 的幂次的区间（ 2k ）预先计算最小值，而不是非重叠块。对于每个索引 i 和带有 i+2k−1<n 的整数 k≥0 ，存储

st[i][k]=min(A[i],A[i+1],…,A[i+2k−1]).

请参见下图（长度为 20=1 的数据块未显示）：

基本情况： st[i][0]=A[i] .递推（通过加倍建立）：

st[i][k]=min(st[i][k−1], st[i+2k−1][k−1]).

下图是 i=0,k=3 （整个数组）的示例：

回答长度为 L=r−l+1 的查询 [l,r] ：

设 k=⌊log2L⌋ (不超过 L 的最大二乘幂）。
使用两个长度为 2k 的预计算块来覆盖查询的两端：ans=min(st[l][k], st[r−2k+1][k]).

由于这两个区间共同覆盖了 [l,r] （可能会重叠），因此它们的最小值等于整个范围内的最小值。这就产生了 O(1) 个查询时间。

请看下图，查询 l=0,r=6 （整个数组）。在这个查询中，我们可以看到 k=2 ，因为 22 是该范围内能容纳的最大的 2 的幂。

请注意，这些区间可以任意重叠--对于 RMQ 来说，重叠是没有问题的，因为多次取最小值不会改变结果。

复杂性

预处理：时间： O(nlogn) ，内存： O(nlogn) （为 0≤i<n 、 0≤k≤⌊log2n⌋ 存储 st[i][k] ）。
查询： O(1) .

摘要

从每个索引（稀疏表）开始，预先计算长度为 2 的幂次的区间的最小值。使用加倍递推法在 O(nlogn) 中建立。在 O(1) 中回答每个 RMQ [l,r] ，方法是将两个重叠的 2 次幂区间组合起来：

k=⌊log2(r−l+1)⌋,ans=min(st[l][k], st[r−2k+1][k]).

st表知识点来自codeforce的某位大神，如果涉及侵权等问题请直接在后台私信我删除，本知识点仅用于题目讲解，不进行商用（总之先叠个甲）

我们先用其查询最大值，再查询最小值，最后将所有查询结果进行比对就好了。这是代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=4e5+5,LG=25;
vector<vector<int>>st(P,vector<int>(LG));
vector<vector<int>>st2(P,vector<int>(LG));
ll check(int l,int mid)
{
    int len=mid-l;
    int k=__lg(len);
    return min(st2[l][k],st2[mid-(1<<k)][k])-max(st[l][k],st[mid-(1<<k)][k]);
}
void solve(){
   int n,q;
   cin>>n;
   vector<int>v(n+1);
   vector<int>r(n+1);
   for(int i=0;i<n;i++)
   {
    cin>>v[i];
    st[i][0]=v[i];
   }
   for(int i=0;i<n;i++)
   {
     cin>>r[i];
     st2[i][0]=r[i];
   }
    for(int k=1;k<LG;k++)
    {
        for(int i=0 ;i+(1<<k)<=n;++i)
        {
            st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
            // cout<<st[i][k]<<endl;
        }
    }
    for(int k=1;k<LG;k++)
    {
        for(int i=0 ;i+(1<<k)<=n;++i)
        {
            st2[i][k]=min(st2[i][k-1],st2[i+(1<<(k-1))][k-1]);
        }
    }
    ll ans=0;
    for(int l=0;l<n;l++)
    {
        int aa1=n+1;
        int aa2=n+1;
        int le=l+1,ri=n;
        while(le<=ri)
        {
            int mid=le+(ri-le)/2;
            if(check(l,mid)<=0)
            {
                ri=mid-1;
                aa1=mid;
            }
            else
            {
                le=mid+1;
            }
        }
         le=l+1,ri=n;
        while(le<=ri)
        {
            int mid=le+(ri-le)/2;
            if(check(l,mid)<0)
            {
                ri=mid-1;
                aa2=mid;
            }
            else
            {
                le=mid+1;
            }
        }
        ans+=(aa2-aa1);
    }
       cout<<ans<<endl;
    
}
int main(){
    int T=1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}