D. Friends and Subsequences

题目连接：

http://www.codeforces.com/contest/689/problem/D

Description

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 while !Mike can instantly tell the value of .

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 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 is satisfied

Sample Input

6

1 2 3 2 1 4

6 7 1 2 3 2

Sample Output

2

Hint

题意

给你一个a数组和一个b数组

问你有多少对(l,r)满足，a数组中max(L,R)恰好等于b数组中的min(L，R)

题解

暴力枚举L，然后二分相等的那个区间就好了。

因为max肯定是递增的，min是递减的

那个相等的区间可以二分出来。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5+7;

int n;

int a[maxn],b[maxn];

struct RMQ{

    const static int RMQ_size = maxn;

	int n;

	int ArrayMax[RMQ_size][21];

	int ArrayMin[RMQ_size][21];

	void build_rmq(){

		for(int j = 1 ; (1<<j) <= n ; ++ j)

			for(int i = 0 ; i + (1<<j) - 1 < n ; ++ i){

				ArrayMax[i][j]=max(ArrayMax[i][j-1],ArrayMax[i+(1<<(j-1))][j-1]);

				ArrayMin[i][j]=min(ArrayMin[i][j-1],ArrayMin[i+(1<<(j-1))][j-1]);

			}

	}

	int QueryMax(int L,int R){

		int k = 0;

		while( (1<<(k+1)) <= R-L+1) k ++ ;

		return max(ArrayMax[L][k],ArrayMax[R-(1<<k)+1][k]);

	}

	int QueryMin(int L,int R){

		int k = 0;

		while( (1<<(k+1)) <= R-L+1) k ++ ;

		return min(ArrayMin[L][k],ArrayMin[R-(1<<k)+1][k]);

	}

	void init(int * a,int sz){

		n = sz ;

		for(int i = 0 ; i < n ; ++ i) ArrayMax[i][0] = ArrayMin[i][0] = a[i];

		build_rmq();

	}

}s1,s2;

int main()

{

    scanf("%d",&n);

    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    for(int i=0;i<n;i++)scanf("%d",&b[i]);

    a[n]=2e9;

    b[n]=-2e9;

    s1.init(a,n+1);

    s2.init(b,n+1);

    long long ans = 0;

    for(int i=0;i<n;i++){

        if(a[i]>b[i])continue;

        int l=i,r=n,ansl=i;

        while(l<=r){

            int mid=(l+r)/2;

            if(s1.QueryMax(i,mid)>=s2.QueryMin(i,mid))r=mid-1,ansl=mid;

            else l=mid+1;

        }

        if(s1.QueryMax(i,ansl)>s2.QueryMin(i,ansl))continue;

        l=i,r=n;

        int ansr=i;

        while(l<=r){

            int mid=(l+r)/2;

            if(s1.QueryMax(i,mid)>s2.QueryMin(i,mid))r=mid-1,ansr=mid;

            else l=mid+1;

        }

        ans+=ansr-ansl;

    }

    cout<<ans<<endl;

}