题意：给定两个整数序列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，最坏情况确实比线段树更快。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <string> 5 #include <cstdlib> 6 #include <cctype> 7 #include <cmath> 8 #include <algorithm> 9 #include <vector> 10 #include <map> 11 #include <set> 12 #include <stack> 13 #include <queue> 14 #include <assert.h> 15 #define FREAD(fn) freopen((fn), "r", stdin) 16 #define RINT(vn) scanf("%d", &(vn)) 17 #define PINT(vb) printf("%d", vb) 18 #define RSTR(vn) scanf("%s", (vn)) 19 #define PSTR(vn) printf("%s", (vn)) 20 #define CLEAR(A, X) memset(A, X, sizeof(A)) 21 #define REP(N) for(int i=0; i<(N); i++) 22 #define REPE(N) for(int i=1; i<=(N); i++) 23 #define pb(X) push_back(X) 24 #define pn() printf("\n") 25 using namespace std; 26 const int MAX_N = (1<<20);//注意要把最大值扩展到2的幂次 27 const int INFP = 0x7fffffff; 28 const int INFN = -0x7fffffff; 29 30 int n, m;//m为大于n的最小的2的幂 31 int a[MAX_N], b[MAX_N]; 32 int ta[MAX_N][32], tb[MAX_N][32];//spare table, t[i][j],i为起点，2^j为区间长度 33 34 void build_max(){ 35 for(int i=n; i<m; i++) a[i] = INFN;//负无穷填充 36 REP(m) ta[i][0] = a[i]; 37 for(int j=1; j<__builtin_ctz(m); j++){//m即区间长度的上限 38 for(int i=0; i+(1<<j) <= m; i++){ 39 ta[i][j] = max(ta[i][j-1], ta[i+(1<<(j-1))][j-1]); 40 } 41 } 42 } 43 44 void build_min(){ 45 for(int i=n; i<m; i++) b[i] = INFP;//正无穷填充 46 REP(m) tb[i][0] = b[i]; 47 for(int j=1; j<__builtin_ctz(m); j++){//m即区间长度的上限 48 for(int i=0; i+(1<<j) <= m; i++){ 49 tb[i][j] = min(tb[i][j-1], tb[i+(1<<(j-1))][j-1]); 50 } 51 } 52 } 53 54 //闭区间 55 int qmax(int l, int r){ 56 int k = log(r-l+1)/log(2.0); 57 return max(ta[l][k], ta[r-(1<<k)+1][k]); 58 } 59 60 int qmin(int l, int r){ 61 int k = log(r-l+1)/log(2.0); 62 return min(tb[l][k], tb[r-(1<<k)+1][k]); 63 } 64 65 //左闭右开，l为起始点 66 int lowerbound(int l){ 67 int lo = l, hi = n;//初始左右界桩 68 int ans = n;//失败返回右界桩 69 while(lo < hi){ 70 int mi = (lo+hi)/2; 71 int qa = qmax(l, mi); 72 int qb = qmin(l, mi); 73 if(qa > qb) hi = mi; 74 else if(qa < qb) lo = mi+1; 75 else{ 76 ans = min(ans, mi);//命中而左移和未命中而左移是不同的！ 77 hi = mi; 78 } 79 80 } 81 return ans; 82 } 83 int upperbound(int l){ 84 int lo = l, hi = n; 85 int ans = -1; 86 while(lo < hi){ 87 int mi = (lo+hi)/2; 88 int qa = qmax(l, mi); 89 int qb = qmin(l, mi); 90 if(qa > qb) hi = mi; 91 else if(qa < qb) lo = mi+1; 92 else{ 93 ans = max(ans, mi); 94 lo = mi+1; 95 } 96 } 97 return ans; 98 } 99 100 int main(){ 101 //FREAD("689d.txt"); 102 RINT(n); 103 m = 1; 104 while(m < n) m <<= 1;//扩展为2的幂 105 REP(n) RINT(a[i]); 106 REP(n) RINT(b[i]); 107 build_max(); 108 build_min(); 109 __int64 ans = 0; 110 int rmin = 0, rmax = 0; 111 REP(n){//for each left end = i, enumerate rmin, rmax 112 rmin = lowerbound(i); 113 rmax = upperbound(i); 114 if(rmin <= rmax) 115 ans += rmax - rmin + 1; 116 //printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax); 117 } 118 cout << ans; 119 return 0;
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <string> 5 #include <cstdlib> 6 #include <cctype> 7 #include <cmath> 8 #include <algorithm> 9 #include <vector> 10 #include <map> 11 #include <set> 12 #include <stack> 13 #include <queue> 14 #include <assert.h> 15 #define FREAD(fn) freopen((fn), "r", stdin) 16 #define RINT(vn) scanf("%d", &(vn)) 17 #define PINT(vb) printf("%d", vb) 18 #define RSTR(vn) scanf("%s", (vn)) 19 #define PSTR(vn) printf("%s", (vn)) 20 #define CLEAR(A, X) memset(A, X, sizeof(A)) 21 #define REP(N) for(int i=0; i<(N); i++) 22 #define REPE(N) for(int i=1; i<=(N); i++) 23 #define pb(X) push_back(X) 24 #define pn() printf("\n") 25 using namespace std; 26 const int MAX_N = (1<<20);//注意要把最大值扩展到2的幂次 27 const int INFP = 0x7fffffff; 28 const int INFN = -0x7fffffff; 29 30 struct Node 31 { 32 int l, r; 33 int v; 34 Node(){} 35 }; 36 37 int n, m;//m为大于n的最小的2的幂 38 int a[MAX_N], b[MAX_N]; 39 Node sta[MAX_N*2], stb[MAX_N*2];//这个是segment tree 40 41 void build_max(int A[], Node AT[], int N){ 42 m = 1; 43 while(m < N) m <<= 1;//m个叶节点，m-1个内部节点，下标从1开始 44 for(int i=0; i<N; i++){ 45 RINT(AT[m+i].v); 46 //AT[m+i].v = A[i];//复制叶节点到m-2m 47 AT[m+i].l = AT[m+i].r = i; 48 } 49 for(int i=N; i<m; i++){ 50 AT[m+i].v = INFN;//末尾用负无穷填充 51 AT[m+i].l = AT[m+i].r = i; 52 } 53 for(int i=m-1; i>=1; i--){//自底向上生成内部节点 54 AT[i].v = max(AT[i*2].v, AT[i*2+1].v); 55 AT[i].l = AT[i*2].l; 56 AT[i].r = AT[i*2+1].r; 57 } 58 // for(int i=1; i<=m*2-1; i++) 59 // printf("%d %d\n", i, AT[i].v); 60 } 61 62 void build_min(int A[], Node AT[], int N){ 63 m = 1; 64 while(m < N) m <<= 1;//m个叶节点，m-1个内部节点，下标从1开始 65 for(int i=0; i<N; i++){ 66 RINT(AT[m+i].v); 67 //AT[m+i].v = A[i];//复制叶节点到m-2m 68 AT[m+i].l = AT[m+i].r = i; 69 } 70 for(int i=N; i<m; i++){ 71 AT[m+i].v = INFP;//末尾用正无穷填充 72 AT[m+i].l = AT[m+i].r = i; 73 } 74 for(int i=m-1; i>=1; i--){//自底向上生成内部节点 75 AT[i].v = min(AT[i*2].v, AT[i*2+1].v); 76 AT[i].l = AT[i*2].l; 77 AT[i].r = AT[i*2+1].r; 78 } 79 // for(int i=1; i<=m*2-1; i++) 80 // printf("%d %d\n", i, AT[i].v); 81 } 82 83 //闭区间,cur为当前子树根 84 int qmax(int cur, int l, int r){//其实l, r在全局的查询中不会变 85 if(l <= sta[cur].l && sta[cur].r <= r){ 86 //printf("hit [%d, %d]\n", sta[cur].l, sta[cur].r); 87 return sta[cur].v;//当前区间包含在目标区间内 88 } 89 if(sta[cur].r < l || sta[cur].l > r) return INFN;//不相交则不再递归 90 else return max(qmax(cur*2, l, r), qmax(cur*2+1, l, r)); 91 } 92 93 int qmin(int cur, int l, int r){ 94 if(l <= stb[cur].l && stb[cur].r <= r) return stb[cur].v; 95 if(stb[cur].r < l || stb[cur].l > r) return INFP; 96 else return min(qmin(cur*2, l, r), qmin(cur*2+1, l, r));//原来min是先算右边的，再算左边的 97 } 98 99 //左闭右开，l为起始点 100 int lowerbound(int lo, int hi, int l){ 101 int ans = n; 102 while(lo < hi){ 103 int mi = (lo+hi)/2; 104 int qa = qmax(1, l, mi); 105 int qb = qmin(1, l, mi); 106 if(qa > qb) hi = mi; 107 else if(qa < qb) lo = mi+1; 108 else{ 109 ans = min(ans, mi);//命中而左移和未命中而左移是不同的！ 110 hi = mi; 111 } 112 113 } 114 return ans; 115 } 116 int upperbound(int lo, int hi, int l){ 117 int ans = 0; 118 while(lo < hi){ 119 int mi = (lo+hi)/2; 120 int qa = qmax(1, l, mi); 121 int qb = qmin(1, l, mi); 122 if(qa > qb) hi = mi; 123 else if(qa < qb) lo = mi+1; 124 else{ 125 ans = max(ans, mi); 126 lo = mi+1; 127 } 128 } 129 return ans; 130 } 131 132 int main(){ 133 FREAD("689d.txt"); 134 RINT(n); 135 build_max(a, sta, n); 136 build_min(b, stb, n); 137 __int64 ans = 0; 138 int rmin = 0, rmax = 0; 139 REP(n){//for each left end = i, enumerate rmin, rmax 140 rmin = lowerbound(i, n, i); 141 if(rmin >= i && rmin < n){//剪枝，rmin存在，则rmax存在 142 rmax = upperbound(rmin, n, i); 143 ans += rmax - rmin + 1; 144 } 145 //if(n == 190593 && i == n/2) break;//这个是为了测试时间，发现跑了一半已经快超时了 146 printf("left = %d, rmin = %d, rmax = %d\n", i, rmin, rmax); 147 } 148 cout << ans; 149 return 0; 150 }
