题意：给定两个整数序列a,b，将a,b对齐，问有多少个区间满足a的区间内最大值等于b的区间内最小值。
数据范围：区间长度n属于[1, 200000]，序列中的元素在整型范围内
思路：枚举所有n*(n+1)/2个区间复杂度过高。题解的方法是，只枚举区间左端点，然后想办法把对右端点的处理降到O(logn)。能降得益于这道题特有的以下性质：
首先，枚举每个左端点时，将左端点left定义为一个常量，将右端点r定义为变量，r >= left；故题目的两个要求可以翻译为这样两个以右端点r为自变量的函数 max{ar}与min{br}，分别表示序列a在区间[left, r]上的最大值，序列b在区间[left, r]上的最小值。
其次，有如下观察事实：
1. 固定左端点，则随着区间的向右扩张，max{ai}不会变小，min{bi}不会变大；即max{ar}单调不降，min{br}单调不升
2. 根据1，可以推出一旦扩张到某个位置出现max{ai} > min{bi}，那么再往右扩张就已经没意义了；对称的，若当前位置仍处在max{ar} < min{br}的状态，那么符合条件的右边界r若存在则一定在当前位置右侧。
3. 根据2，可以推出符合条件的右边界r如果存在，则一定连续分布在left右侧的某个区间内。
所以，根据以上性质，尤其第3条，我们便可以使用二分查找来加速原来的对右边界的枚举。假设合法的右边界构成了区间[rmin, rmax]，那么分别二分查找rmin, rmax即可。类似lower_bound和upper_bound，对rmin和rmax二分查找的区别仅在于相等时的移动方向：rmin左移而rmax右移。另外注意对查找失败情况的处理，查找前初始化rmin为n-1, rmax为left，这样查找失败<=>rmax < rmin，这种情况不为最终的结果贡献长度。
这样确定一个rmin需要二分logn个位置*每个位置logn的求最值，共计log2n；因此总的时间为n*2log2n = n*log2(n2)
区间查询部分题解说用任意一个可以做RMQ的数据结构即可，于是想借此试试线段树，结果T了。。。然后剪枝，当rmin不合法时continue。然而还是会T，因为最坏情况无法避免n*2log2n的总时间。于是学习别人的姿势改用sparse table，这样需nlogn的预处理，但每个位置求最值只需O(1)，所以总的时间为nlogn + n，最坏情况确实比线段树更快。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(int i=0; i<(N); i++)
#define REPE(N) for(int i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = (<<);//注意要把最大值扩展到2的幂次
const int INFP = 0x7fffffff;
const int INFN = -0x7fffffff; int n, m;//m为大于n的最小的2的幂
int a[MAX_N], b[MAX_N];
int ta[MAX_N][], tb[MAX_N][];//spare table, t[i][j],i为起点，2^j为区间长度 void build_max(){
for(int i=n; i<m; i++) a[i] = INFN;//负无穷填充
REP(m) ta[i][] = a[i];
for(int j=; j<__builtin_ctz(m); j++){//m即区间长度的上限
for(int i=; i+(<<j) <= m; i++){
ta[i][j] = max(ta[i][j-], ta[i+(<<(j-))][j-]);
}
}
} void build_min(){
for(int i=n; i<m; i++) b[i] = INFP;//正无穷填充
REP(m) tb[i][] = b[i];
for(int j=; j<__builtin_ctz(m); j++){//m即区间长度的上限
for(int i=; i+(<<j) <= m; i++){
tb[i][j] = min(tb[i][j-], tb[i+(<<(j-))][j-]);
}
}
} //闭区间
int qmax(int l, int r){
int k = log(r-l+)/log(2.0);
return max(ta[l][k], ta[r-(<<k)+][k]);
} int qmin(int l, int r){
int k = log(r-l+)/log(2.0);
return min(tb[l][k], tb[r-(<<k)+][k]);
} //左闭右开，l为起始点
int lowerbound(int l){
int lo = l, hi = n;//初始左右界桩
int ans = n;//失败返回右界桩
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(l, mi);
int qb = qmin(l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = min(ans, mi);//命中而左移和未命中而左移是不同的！
hi = mi;
} }
return ans;
}
int upperbound(int l){
int lo = l, hi = n;
int ans = -;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(l, mi);
int qb = qmin(l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = max(ans, mi);
lo = mi+;
}
}
return ans;
} int main(){
//FREAD("689d.txt");
RINT(n);
m = ;
while(m < n) m <<= ;//扩展为2的幂
REP(n) RINT(a[i]);
REP(n) RINT(b[i]);
build_max();
build_min();
__int64 ans = ;
int rmin = , rmax = ;
REP(n){//for each left end = i, enumerate rmin, rmax
rmin = lowerbound(i);
rmax = upperbound(i);
if(rmin <= rmax)
ans += rmax - rmin + ;
//printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
}
cout << ans;
return ;
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(int i=0; i<(N); i++)
#define REPE(N) for(int i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = (<<);//注意要把最大值扩展到2的幂次
const int INFP = 0x7fffffff;
const int INFN = -0x7fffffff; struct Node
{
int l, r;
int v;
Node(){}
}; int n, m;//m为大于n的最小的2的幂
int a[MAX_N], b[MAX_N];
Node sta[MAX_N*], stb[MAX_N*];//这个是segment tree void build_max(int A[], Node AT[], int N){
m = ;
while(m < N) m <<= ;//m个叶节点，m-1个内部节点，下标从1开始
for(int i=; i<N; i++){
RINT(AT[m+i].v);
//AT[m+i].v = A[i];//复制叶节点到m-2m
AT[m+i].l = AT[m+i].r = i;
}
for(int i=N; i<m; i++){
AT[m+i].v = INFN;//末尾用负无穷填充
AT[m+i].l = AT[m+i].r = i;
}
for(int i=m-; i>=; i--){//自底向上生成内部节点
AT[i].v = max(AT[i*].v, AT[i*+].v);
AT[i].l = AT[i*].l;
AT[i].r = AT[i*+].r;
}
// for(int i=1; i<=m*2-1; i++)
// printf("%d %d\n", i, AT[i].v);
} void build_min(int A[], Node AT[], int N){
m = ;
while(m < N) m <<= ;//m个叶节点，m-1个内部节点，下标从1开始
for(int i=; i<N; i++){
RINT(AT[m+i].v);
//AT[m+i].v = A[i];//复制叶节点到m-2m
AT[m+i].l = AT[m+i].r = i;
}
for(int i=N; i<m; i++){
AT[m+i].v = INFP;//末尾用正无穷填充
AT[m+i].l = AT[m+i].r = i;
}
for(int i=m-; i>=; i--){//自底向上生成内部节点
AT[i].v = min(AT[i*].v, AT[i*+].v);
AT[i].l = AT[i*].l;
AT[i].r = AT[i*+].r;
}
// for(int i=1; i<=m*2-1; i++)
// printf("%d %d\n", i, AT[i].v);
} //闭区间,cur为当前子树根
int qmax(int cur, int l, int r){//其实l, r在全局的查询中不会变
if(l <= sta[cur].l && sta[cur].r <= r){
//printf("hit [%d, %d]\n", sta[cur].l, sta[cur].r);
return sta[cur].v;//当前区间包含在目标区间内
}
if(sta[cur].r < l || sta[cur].l > r) return INFN;//不相交则不再递归
else return max(qmax(cur*, l, r), qmax(cur*+, l, r));
} int qmin(int cur, int l, int r){
if(l <= stb[cur].l && stb[cur].r <= r) return stb[cur].v;
if(stb[cur].r < l || stb[cur].l > r) return INFP;
else return min(qmin(cur*, l, r), qmin(cur*+, l, r));//原来min是先算右边的，再算左边的
} //左闭右开，l为起始点
int lowerbound(int lo, int hi, int l){
int ans = n;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(, l, mi);
int qb = qmin(, l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = min(ans, mi);//命中而左移和未命中而左移是不同的！
hi = mi;
} }
return ans;
}
int upperbound(int lo, int hi, int l){
int ans = ;
while(lo < hi){
int mi = (lo+hi)/;
int qa = qmax(, l, mi);
int qb = qmin(, l, mi);
if(qa > qb) hi = mi;
else if(qa < qb) lo = mi+;
else{
ans = max(ans, mi);
lo = mi+;
}
}
return ans;
} int main(){
FREAD("689d.txt");
RINT(n);
build_max(a, sta, n);
build_min(b, stb, n);
__int64 ans = ;
int rmin = , rmax = ;
REP(n){//for each left end = i, enumerate rmin, rmax
rmin = lowerbound(i, n, i);
if(rmin >= i && rmin < n){//剪枝，rmin存在，则rmax存在
rmax = upperbound(rmin, n, i);
ans += rmax - rmin + ;
}
//if(n == 190593 && i == n/2) break;//这个是为了测试时间，发现跑了一半已经快超时了
printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax);
}
cout << ans;
return ;
}
T了的线段树