Codeforces 689D Friends and Subsequences【思维+二分+RMQ】套路题

D. Friends and Subsequences time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output

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 a₁, a₂, ..., a_n ( - 10⁹ ≤ a_i ≤ 10⁹) — the sequence a.

The third line contains n integer numbers b₁, b₂, ..., b_n ( - 10⁹ ≤ b_i ≤ 10⁹) — the sequence b.

Output

Print the only integer number — the number of occasions the robot will count, thus for how many pairs is satisfied.

Examples Input 6 1 2 3 2 1 4 6 7 1 2 3 2 Output 2 Input 3 3 3 3 1 1 1 Output 0 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的序列，问你有多少个区间【l，r】使得max（a【i】）【l<=i<=r】==min（b【i】）【l<=i<=r】;

思路：

1、求区间内最大最小值，显然这是RMQ问题，要么用线段树来维护，要么用ST倍增预处理，这个题显然不需要动态维护，那么为了节省代码量，肯定ST倍增预处理是一个很好的选择。

2、接下来考虑到，对于一个数组来讲，如果起点l确定了，那么随着r的增加，最大值可能越来越大，最小值可能越来越小。那么这里确实存在一个单调性，那么我们考虑二分终点位子r.

那么有几种情况：

①maxn<minn，那么我们增大l，使得A【】的最大值加大，并且尽可能的使得B【】最小值减小，才可能相等。

②maxn==minn，显然是可行解。

③maxn>minn，那么我们需要减小r，道理同上。

接下来再考虑到一个l可能对应多个r是可行解，那么我们二分最左端的可行位子posl，以及二分最右端的可行位子posr，那么ans+=posr-posl+1；

注意点常数。

第一发查询稍微多了几个步骤，就TLE掉了。

Ac代码：

#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> using namespace std; int a[200005]; int b[200005]; int maxn[200005][20]; int minn[200005][20]; int n,q; void ST() { int len=floor(log10(double(n))/log10(double(2))); for(int j=1;j<=len;j++) { for(int i=1;i<=n+1-(1<<j);i++) { maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]); minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); } } } int getmaxn(int a,int b) { int len= floor(log10(double(b-a+1))/log10(double(2))); return max(maxn[a][len], maxn[b-(1<<len)+1][len]); } int getminn(int a,int b) { int len= floor(log10(double(b-a+1))/log10(double(2))); return min(minn[a][len], minn[b-(1<<len)+1][len]); } int erfen1(int ss) { int ans=-1; int l=ss; int r=n; while(r-l>=0) { int mid=(l+r)/2; int maxn=getmaxn(ss,mid); int minn=getminn(ss,mid); if(maxn<minn) { l=mid+1; } else { if(maxn==minn)ans=mid; r=mid-1; } } return ans; } int erfen2(int ss) { int ans=-1; int l=ss; int r=n; while(r-l>=0) { int mid=(l+r)/2; int maxn=getmaxn(ss,mid); int minn=getminn(ss,mid); if(maxn<=minn) { if(maxn==minn)ans=mid; l=mid+1; } else { r=mid-1; } } return ans; } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxn[i][0]=a[i]; for(int i=1;i<=n;i++)scanf("%d",&b[i]),minn[i][0]=b[i]; ST(); __int64 output=0; for(int i=1;i<=n;i++) { int posl=erfen1(i); int posr=erfen2(i); if(posl==-1||posr==-1)continue; else output+=posr-posl+1; } printf("%I64d\n",output); } }