【打CF，学算法——四星级】CodeForces 689D Friends and Subsequences （RMQ+二分）

The occasions in the first sample case are:

1.l = 4,r = 4 sincemax{2} = min{2}.

2.l = 4,r = 5 sincemax{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.

题意：

    给定两个等长区间，求相同l,r情况下，有多少个区间，第一个序列的最大值和第二个序列的最小值相同。

解题：

    RMQ，O（nlog（n））的复杂度，随后可以做到O（1）询问。但若枚举区间l，r，复杂度仍为O(n^2)。这时可以利用区间特性进行二分，固定区间左端点（注意区间左端点和二分左端点不一样），若二分右端点所在位置形成的最小值不等于最大值，若最小值大于最大值，说明仍可以右移，还有希望相等。若最小值小于最大值，则说明区间过长，左移区间左端点。若相等，则根据当前是求右边界最左端还是最右端进行相应移动。

    此题比较特殊的是，枚举左区间端点，但左区间端点和左二分端点是不一样的，二分的是区间右端点。每次通过两次二分，求出每一区间左端点对应的区间右端点的两个位置极值，作差，求和，求得结果。

代码：

#include <iostream>
#include <cstdio>
#define maxn 200010
#define LL long long
using namespace std;
int a[maxn],b[maxn];
int n;
int ma[maxn][20],mi[maxn][20];
void cal()
{for(int i=0;i<n;i++){ma[i][0]=a[i];mi[i][0]=b[i];}for(int j=1;(1<<j)<=n;j++){for(int i=0;i+(1<<j)-1<n;i++){ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int RMQmax(int le,int ri)
{int k=0;while((1<<(k+1))<=ri-le+1)k++;return max(ma[le][k],ma[ri-(1<<k)+1][k]);
}
int RMQmin(int le,int ri)
{int k=0;while((1<<(k+1))<=ri-le+1)k++;return min(mi[le][k],mi[ri-(1<<k)+1][k]);
}
int main()
{LL ans=0,le,ri,tmp1,tmp2,va,vi;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]);cal();for(int i=0;i<n;i++){le=i;ri=n-1;tmp1=-1;while(le<=ri){int mid=(le+ri)>>1;vi=RMQmin(i,mid);va=RMQmax(i,mid);if(vi==va){ri=mid-1;tmp1=mid;}else if(vi>va){le=mid+1;}else{ri=mid-1;}}if(tmp1!=-1){le=i;ri=n-1;while(le<=ri){int mid=(le+ri)>>1;vi=RMQmin(i,mid);va=RMQmax(i,mid);if(vi==va){le=mid+1;tmp2=mid;}else if(vi>va){le=mid+1;}else{ri=mid-1;}}ans+=tmp2-tmp1+1;}}printf("%lld\n",ans);return 0;
}