Codeforces Round #361 (Div. 2) D Friends and Subsequences
题目链接：
题意：给定两个长度相同的数组，a和b。问你在相同的区间中amax=bmin的区间有多少个，数组的范围为200000.
解法：我们可以枚举起始点，然后用二分查到amax和bmin相等的左右端点，然后进行区间累加就可以了。对于最大值最小值的查询我们可以采用线段树和RMQ来优化。线段树的查询复杂度是log（n），RMQ是O（1）的。
线段树版本：
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ll __int64
#define maxn 2000008
const ll inf=1e16;
struct T
{
int l,r,maxx;
}t[4*maxn],t1[4*maxn];
ll cnt=0;
int a[maxn],b[maxn];
void a_build(int id,int l,int r)
{
int tt=id<<1;
t[id].l=l,t[id].r=r;
if(l==r) t[id].maxx=a[l];
else
{
int mid=(l+r)>>1;
a_build(tt,l,mid);
a_build(tt|1,mid+1,r);
t[id].maxx=max(t[tt].maxx,t[tt|1].maxx);
}
return ;
}
void b_build(int id,int l,int r)
{
int tt=id<<1;
t1[id].l=l,t1[id].r=r;
if(l==r)
{
t1[id].maxx=b[l];
}
else
{
int mid=(l+r)>>1;
b_build(tt,l,mid);
b_build(tt|1,mid+1,r);
t1[id].maxx=min(t1[tt].maxx,t1[tt|1].maxx);
}
}
int a_query(int id,int l,int r)
{
int tt=id<<1;
if(t[id].l>=l&&t[id].r<=r) return t[id].maxx;
else
{
int mid=(t[id].l+t[id].r)>>1;
if(l>mid) return a_query(tt|1,l,r);
else if(r<=mid) return a_query(tt,l,r);
else return max(a_query(tt|1,mid+1,r),a_query(tt,l,mid));
}
}
int b_query(int id,int l,int r)
{
int tt=id<<1;
if(t1[id].l>=l&&t1[id].r<=r) return t1[id].maxx;
else
{
int mid=(t1[id].l+t1[id].r)>>1;
if(l>mid) return b_query(tt|1,l,r);
else if(r<=mid) return b_query(tt,l,r);
else return min(b_query(tt|1,mid+1,r),b_query(tt,l,mid));
}
}
int check(int l,int r)
{
int amax,bmin;
amax=a_query(1,l,r);
bmin=b_query(1,l,r);
//cout<<"ll: "<<l<<" r "<<r<<endl;
// cout<<"amax "<<amax<<" bmin "<<bmin<<endl;
if(amax==bmin) return 1;
if(amax>bmin) return 0;
if(amax<bmin) return 2;
}
int main(void)
{
// freopen(&#","r",stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
a_build(1,1,n);
b_build(1,1,n);
cnt=0;
for(int i=1;i<=n;i++)
{
int l=i,r=n+1;
int L,R;
L=R=-1;
while(l<r)
{
// cout<<"xxx"<<i<<" "<<l<<" "<<r<<endl;
int mid=l+(r-l)/2;
int m=check(i,mid);
if(m==0||m==1)
{
r=mid;
}
else l=mid+1;
if(m==1) L=mid;
}
if(L==-1) continue;
l=L,r=n+1;
while(l<r)
{
int mid=l+(r-l)/2;
int m=check(i,mid);
if(m==0)
{
r=mid;
}
else l=mid+1;
if(m==1) R=mid;
}
//cout<<"xxx"<<i<<" "<<L<<" "<<R<<endl;
cnt+=(R-L+1);
}
printf("%I64dn",cnt);
}
RMQ版本：
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ll __int64
#define maxn 200008
const ll inf=1e16;
ll cnt;
int n;
int a[maxn],b[maxn],d1[maxn][20],d2[maxn][20];
void RMQ()
{
for(int i=0;i<n;i++) d1[i][0]=a[i],d2[i][0]=b[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=0;i+(1<<j)-1<n;i++)
{
d1[i][j]=max(d1[i][j-1],d1[i+(1<<(j-1))][j-1]);
d2[i][j]=min(d2[i][j-1],d2[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r,int f)
{
int k=0;
while((1<<(k+1))<=r-l+1) k++;
if(f==1) return max(d1[l][k],d1[r-(1<<k)+1][k]);
return min(d2[l][k],d2[r-(1<<k)+1][k]);
}
int check(int l,int r)
{
int amax,bmin;
amax=query(l,r,1);
bmin=query(l,r,2);
//cout<<"ll: "<<l<<" r "<<r<<endl;
// cout<<"amax "<<amax<<" bmin "<<bmin<<endl;
if(amax==bmin) return 1;
if(amax>bmin) return 0;
if(amax<bmin) return 2;
}
int main(void)
{
// freopen(&#","r",stdin);
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]);
RMQ();
cnt=0;
for(int i=0;i<n;i++)
{
int l=i,r=n;
int L,R;
L=R=-1;
while(l<r)
{
// cout<<"xxx"<<i<<" "<<l<<" "<<r<<endl;
int mid=l+(r-l)/2;
int m=check(i,mid);
if(m==0||m==1)
{
r=mid;
}
else l=mid+1;
if(m==1) L=mid;
}
if(L==-1) continue;
l=L,r=n;
while(l<r)
{
int mid=l+(r-l)/2;
int m=check(i,mid);
if(m==0)
{
r=mid;
}
else l=mid+1;
if(m==1) R=mid;
}
//cout<<"xxx"<<i<<" "<<L<<" "<<R<<endl;
cnt+=(R-L+1);
}
printf("%I64dn",cnt);
}
