Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#include <ext/pb_ds/assoc_container.hpp>
- //using namespace __gnu_pbds;
- using namespace std;
- //template<typename T>
- //using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- //#pragma GCC optimize("O3,unroll-loops")
- //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
- typedef long long ll;
- #define pw(x) (1ll << x)
- #define all(x) (x).begin(), (x).end()
- #define mt(x) (x << 1ll)
- #define sz(x) (int)(x).size()
- #define sqr(x) (x) * (x)
- const int mod = 1e9 + 7;
- const int inf = 1e9;
- const ll linf = 1e18;
- const int maxn = 2e5 + 1;
- const int lg = 20;
- int n, m, a[maxn], st[maxn][lg];
- int suff[maxn];
- int get(int l, int r) {
- int j = __lg(r - l + 1);
- return min(st[l][j], st[r - pw(j) + 1][j]);
- }
- int get_left(int l, int r) {
- while (l < r) {
- int mid = (l + r) >> 1;
- if (a[mid] == a[r]) {
- r = mid;
- } else {
- l = mid + 1;
- }
- }
- return l;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- }
- suff[n] = st[n][0] = 0;
- for (int i = n - 1; i >= 1; i--) {
- if (a[i] == a[n]) continue;
- suff[i] = max(0, suff[i + 1] - (a[i + 1] - a[i]) + 1);
- st[i][0] = suff[i];
- }
- for (int j = 1; j < lg; j++) {
- for (int i = 1; i + pw(j) - 1 <= n; i++) {
- st[i][j] = min(st[i][j - 1], st[i + pw(j - 1)][j - 1]);
- }
- }
- cin >> m;
- while (m--) {
- int l, r;
- cin >> l >> r;
- cout << a[r] - a[l] + suff[l] - get(l, get_left(l, r)) << '\n';
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment