Friends and Subsequences-白红宇

Friends and Subsequences

阅读量：5108 次

发布时间：2019-06-13

本文共 2671 字，大约阅读时间需要 8 分钟。

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 exactlyn(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

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

output

input

3 3 3 3 1 1 1

output

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.

分析:RMQ+二分；

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                     
                      ::iterator it=s.begin();it!=s.end();it++)#define vi vector
                      
                       #define pii pair
                       
                        #define mod 1000000007#define inf 0x3f3f3f3f#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)const int maxn=2e5+10;const int dis[][2]={ 0,1,-1,0,0,-1,1,0};using namespace std;using namespace __gnu_cxx;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,p[maxn],a[20][maxn],b[20][maxn];ll ans;void init(){ for(int i=2;i
                        
                         1) { int mid=(l+r)>>1; if(getma(now,mid)
                         
                          1) { int mid=(l+r)>>1; if(getma(now,mid)<=getmi(now,mid))l=mid; else r=mid; } return r;}int main(){ int i,j,k,t; scanf("%d",&n); rep(i,0,n-1)scanf("%d",&a[0][i]); rep(i,0,n-1)scanf("%d",&b[0][i]); init(); rep(i,0,n-1)ans+=getr(i)-getl(i); printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/dyzll/p/5666140.html

你可能感兴趣的文章