Codeforces Round #361 (Div. 2) D. Friends and Subsequences RMQ+二分

链接：

http://codeforces.com/contest/689/problem/D

题意：

给出两个数组，问有多少个区间l，r满足

题解：

先用st表预先处理任意一个区间的最值，然后枚举每个左端点，二分找到满足条件的最近和最远的右端点即可

代码：

31 int n;
32 int a[MAXN], b[MAXN];
33 int st_min[MAXN][32], st_max[MAXN][32];
34 
35 void init() {
36     per(i, 0, n) {
37         st_max[i][0] = a[i];
38         st_min[i][0] = b[i];
39         for (int j = 1; (i + (1 << j) - 1) < n; j++) {
40             st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << j - 1)][j - 1]);
41             st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << j - 1)][j - 1]);
42         }
43     }
44 }
45 
46 int query_max(int l, int r) {
47     int k = log2(r - l + 1);
48     return max(st_max[l][k], st_max[r - (1 << k) + 1][k]);
49 }
50 
51 int query_min(int l, int r) {
52     int k = log2(r - l + 1);
53     return min(st_min[l][k], st_min[r - (1 << k) + 1][k]);
54 }
55 
56 int main() {
57     ios::sync_with_stdio(false), cin.tie(0);
58     cin >> n;
59     rep(i, 0, n) cin >> a[i];
60     rep(i, 0, n) cin >> b[i];
61     init();
62     ll ans = 0;
63     rep(i, 0, n) {
64         if (a[i] > b[i]) continue;
65         int beg = -1, end = -1;
66         int l = i, r = n - 1;
67         while (l <= r) {
68             int mid = (l + r) / 2;
69             if (query_max(i, mid) == query_min(i, mid)) beg = mid;
70             if (query_max(i, mid) >= query_min(i, mid)) r = mid - 1;
71             else l = mid + 1;
72         }
73         if (beg == -1) continue;
74         l = i, r = n - 1;
75         while (l <= r) {
76             int mid = (l + r) / 2;
77             if (query_max(i, mid) == query_min(i, mid)) end = mid;
78             if (query_max(i, mid) > query_min(i, mid)) r = mid - 1;
79             else l = mid + 1;
80         }
81         ans += end - beg + 1;
82     }
83     cout << ans << endl;
84     return 0;
85 }