L题题解（镜影）

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

https://codeforces.com/edu/course/3/lesson/18/2

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

这是代码：

#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;
}