Codefoeces-689D Friends and Subsequences

Friends and Subsequences

Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows?

Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l, r), Mike can instantly tell the value of $\text{[math]}$ while !Mike can instantly tell the value of $\text{[math]}$ .

Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l, r) (1 ≤ l ≤ r ≤ n) (so he will make exactly n(n + 1) / 2 queries) and counts how many times their answers coincide, thus for how many pairs $\text{[math]}$ is satisfied.

How many occasions will the robot count?

Input

The first line contains only integer n (1 ≤ n ≤ 200 000).

The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence a.

The third line contains n integer numbers b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) — the sequence b.

Output

Print the only integer number — the number of occasions the robot will count, thus for how many pairs $\text{[math]}$ is satisfied.

Examples

input

Copy

6
1 2 3 2 1 4
6 7 1 2 3 2

output

Copy

input

Copy

3
3 3 3
1 1 1

output

Copy

Note

The occasions in the first sample case are:

1.l = 4,r = 4 since max{2} = min{2}.

2.l = 4,r = 5 since max{2, 1} = min{2, 3}.

There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.

题意:给出两个长度为n的序列，求有哪些区间相同的 a区间最大值==b区间最小值

思路：预处理出ST表,然后我们来遍历1~n每次我们查询最左的符合要求的右端点，再查询出最右的符合要求的右端点。这样最右-最左就为符合的区间，累加即可。我们在查询端点时，二分查询就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 201000;
ll Max[maxn][30],Min[maxn][30],b[maxn],a[maxn],n;
void GetST()
{
    for(int i=1; i<=n; i++)
    {
        Max[i][0]=a[i];
        Min[i][0]=b[i];
    }
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
        {
            int k=j-1;
            Max[i][j]=max(Max[i][k],Max[i+(1<<k)][k]);
            Min[i][j]=min(Min[i][k],Min[i+(1<<k)][k]);
        }
}
ll getmax(int l,int r)
{
    int k=(int)(log(r-l+1)/log(2.0));
    return max(Max[l][k],Max[r-(1<<k)+1][k]);
}
ll getmin(int l,int r)
{
    int k=(int)(log(r-l+1)/log(2.0));
    return min(Min[l][k],Min[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    for(int i=1; i<=n; i++)
        scanf("%lld",&b[i]);
    GetST();
    ll ans=0;
    int l,r,m;
    int idl,idr;
    for(int i=1; i<=n; i++)
    {
        l=i;
        r=n;
        idl=0,idr=0;
        while(l<=r)
        {
            m=(l+r)>>1;
            ll Maxx=getmax(i,m);
            ll Minx=getmin(i,m);
            if(Maxx==Minx)
            {
                idr=m;
                l=m+1;
            }//查询最右
            else if(Maxx<Minx)
                l=m+1;
            else r=m-1;
        }
        if(idr)
        {
            l=i;
            r=n;
            while(l<=r)
            {
                m=(l+r)>>1;
                ll Maxx=getmax(i,m);
                ll Minx=getmin(i,m);
                if(Maxx==Minx)
                {
                    idl=m;
                    r=m-1;
                }//查询最左
                else if(Maxx<Minx)
                    l=m+1;
                else r=m-1;
            }
            ans+=idr-idl+1;
        }
    }
    printf("%lld
",ans);
}

View Code

PS：摸鱼怪的博客分享，欢迎感谢各路大牛的指点~