D. Friends and Subsequences

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5  6 const int maxn = 200000 + 10; 7 int n, a[maxn], b[maxn]; 8 int d_min[maxn][30]; 9 int d_max[maxn][30];10 11 void RMQ_init() {12     for (int i = 0; i<n; i++) d_max[i][0] = a[i], d_min[i][0] = b[i];13     for (int j = 1; (1 << j) <= n; j++)14         for (int i = 0; i + (1 << j) - 1 < n; i++) {15             d_min[i][j] = min(d_min[i][j - 1], d_min[i + (1 << (j - 1))][j - 1]);16             d_max[i][j] = max(d_max[i][j - 1], d_max[i + (1 << (j - 1))][j - 1]);17         }18 }19 20 int RMQ_min(int L, int R) {21     int k = 0;22     while ((1 << (k + 1)) <= R - L + 1) k++;23     return min(d_min[L][k], d_min[R - (1 << k) + 1][k]);24 }25 26 int RMQ_max(int L, int R) {27     int k = 0;28     while ((1 << (k + 1)) <= R - L + 1) k++;29     return max(d_max[L][k], d_max[R - (1 << k) + 1][k]);30 }31 32 int main()33 {34     cin >> n;35     for (int i = 0; i < n; i++) scanf("%d", &a[i]);36     for (int i = 0; i < n; i++) scanf("%d", &b[i]);37     RMQ_init();38     long long ans = 0;39     for (int i = 0; i < n; i++) {40         if (a[i] > b[i]) continue;41         int first_r = -1, last_r = -1;42         int l = i, r = n - 1, mid;43 44         while (l <= r) {45             mid = (l + r) / 2;46             if (RMQ_max(i, mid) == RMQ_min(i, mid)) first_r = mid;47             if (RMQ_max(i, mid) >= RMQ_min(i, mid)) r = mid - 1;48             else l = mid + 1;49         }50         if (first_r == -1) continue;51 52         l = i; r = n - 1;53         while (l <= r) {54             mid = (l + r) / 2;55             if (RMQ_max(i, mid) > RMQ_min(i, mid))56                 r = mid - 1;57             else l = mid + 1, last_r = mid;58         }59 60         ans += last_r - first_r + 1;61     }62     cout << ans << endl;63     return 0;64 }