Friends and Subsequences
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?
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.
Print the only integer number — the number of occasions the robot will count, thus for how many pairs is satisfied.
6
1 2 3 2 1 4
6 7 1 2 3 2
2
3
3 3 3
1 1 1
0
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的序列，求有哪些区间相同的 a区间最大值==b区间最小值
思路：预处理出ST表,然后我们来遍历1~n每次我们查询最左的符合要求的右端点，再查询出最右的符合要求的右端点。这样最右-最左就为符合的区间，累加即可。我们在查询端点时，二分查询就行。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 201000; ll Max[maxn][30],Min[maxn][30],b[maxn],a[maxn],n; void GetST() { for(int i=1; i<=n; i++) { Max[i][0]=a[i]; Min[i][0]=b[i]; } for(int j=1; (1<<j)<=n; j++) for(int i=1; i+(1<<j)-1<=n; i++) { int k=j-1; Max[i][j]=max(Max[i][k],Max[i+(1<<k)][k]); Min[i][j]=min(Min[i][k],Min[i+(1<<k)][k]); } } ll getmax(int l,int r) { int k=(int)(log(r-l+1)/log(2.0)); return max(Max[l][k],Max[r-(1<<k)+1][k]); } ll getmin(int l,int r) { int k=(int)(log(r-l+1)/log(2.0)); return min(Min[l][k],Min[r-(1<<k)+1][k]); } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%lld",&a[i]); for(int i=1; i<=n; i++) scanf("%lld",&b[i]); GetST(); ll ans=0; int l,r,m; int idl,idr; for(int i=1; i<=n; i++) { l=i; r=n; idl=0,idr=0; while(l<=r) { m=(l+r)>>1; ll Maxx=getmax(i,m); ll Minx=getmin(i,m); if(Maxx==Minx) { idr=m; l=m+1; }//查询最右 else if(Maxx<Minx) l=m+1; else r=m-1; } if(idr) { l=i; r=n; while(l<=r) { m=(l+r)>>1; ll Maxx=getmax(i,m); ll Minx=getmin(i,m); if(Maxx==Minx) { idl=m; r=m-1; }//查询最左 else if(Maxx<Minx) l=m+1; else r=m-1; } ans+=idr-idl+1; } } printf("%lld\n",ans); }
PS：摸鱼怪的博客分享，欢迎感谢各路大牛的指点~
Codefoeces-689D Friends and Subsequences
原文：https://www.cnblogs.com/MengX/p/9134829.html
