tests/yosupo/static-rmq.test.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:43-03:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• bits/stdc++.h
• ds/StaticRMQ.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>
#include "ds/StaticRMQ.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

using namespace lib;

int32_t main(){
    // Scanner sc(stdin);
    // Printer pr(stdout);
    iopt;

    int n, Q;
    cin >> n >> Q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    StaticRMQ<int> rmq(a);

    while(Q--) {
      int l, r;
      cin >> l >> r;
      --r;
      cout << rmq.query(l, r) << "\n";
    }
    return 0;
}

#line 1 "tests/yosupo/static-rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>
#line 1 "ds/StaticRMQ.cpp"


#line 4 "ds/StaticRMQ.cpp"

namespace lib {
using namespace std;
namespace {
  inline int lsb(int x) { return x&-x; }
}

// Credits: hly1204
template<typename T, typename Cmp = std::less<T>>
struct StaticRMQ {
  Cmp cmp;
  vector<T> t1, t2, a;

  StaticRMQ() {}

  StaticRMQ(const vector<T>& a)
    : t1(a.size() + 1), t2(a.size() + 1), a(a) {
    copy(a.begin(), a.end(), t1.begin() + 1);
    copy(a.begin(), a.end(), t2.begin() + 1);
    build();
  }

  int size() const { return (int)t1.size() - 1; }

  T best(const T& a, const T& b) const {
    return cmp(a, b) ? a : b;
  }

  void build() {
    int n = size();
    for(int i = 1; i <= n; i++) {
      int b = lsb(i);
      if(i + b <= n) t1[i + b] = best(t1[i + b], t1[i]);
    }
    for(int i = n; i; i--) {
      int b = lsb(i);
      t2[i - b] = best(t2[i - b], t2[i]);
    }
  }

  // [l, r], 0-indexed
  T query(int l, int r) const {
    if(l == r) return a[l];
    ++l, ++r;
    T ans = best(a[l-1], a[r-1]);
    int x = l;
    for(; x + lsb(x) - 1 <= r; x += lsb(x))
      ans = best(ans, t2[x]);
    for(int y = r; y != 0 && y - lsb(y) + 1 >= l; y -= lsb(y))
      ans = best(ans, t1[y]);
    if(x <= r)
      ans = best(ans, a[x-1]);
    return ans;
  }
};
} // namespace lib



#line 5 "tests/yosupo/static-rmq.test.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

using namespace lib;

int32_t main(){
    // Scanner sc(stdin);
    // Printer pr(stdout);
    iopt;

    int n, Q;
    cin >> n >> Q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    StaticRMQ<int> rmq(a);

    while(Q--) {
      int l, r;
      cin >> l >> r;
      --r;
      cout << rmq.query(l, r) << "\n";
    }
    return 0;
}

Back to top page