結果

問題 No.875 Range Mindex Query
ユーザー nu50218
提出日時 2019-09-08 22:40:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 271 ms / 2,000 ms
コード長 4,842 bytes
コンパイル時間 1,848 ms
コンパイル使用メモリ 180,404 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-06-27 15:17:20
合計ジャッジ時間 4,490 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;
/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))
/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;
/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;
/* func */
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}
/* library */
template <typename T>
struct SegmentTree {
   private:
    size_t length;
    vector<T> data;
    function<T(T, T)> f;
    T e;
    //data[i]の区間 = [l[i],r[i])
    vector<int> l;
    vector<int> r;
   public:
    void change(int i, T val) {
        data[i + length - 1] = val;
        for (int k = (i + length) / 2 - 1; k >= 0; k = (k - 1) / 2) {
            data[k] = f(data[2 * k + 1], data[2 * k + 2]);
            if (!k) break;
        }
    }
    //[i,j)
    T query(const int &i, const int &j) {
        T ans = e;
        queue<int> que;
        que.push(0);
        int k;
        while (que.size()) {
            k = que.front();
            que.pop();
            if (r[k] <= i || j <= l[k]) {
                continue;
            }
            if (i <= l[k] && r[k] <= j) {
                ans = f(ans, data[k]);
                continue;
            }
            que.push(2 * k + 1);
            que.push(2 * k + 2);
        }
        return ans;
    }
    SegmentTree(const vector<T> &v, const function<T(T, T)> &f, const T &e) : length(1), f(f), e(e) {
        while (!(length >= v.size())) length *= 2;
        data = vector<T>(length * 2 - 1, e);
        for (int i = 0; i < v.size(); i++) {
            data[i + length - 1] = v[i];
        }
        for (int i = length - 2; 0 <= i; i--) {
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
        }
        l.resize(length * 2 - 1);
        r.resize(length * 2 - 1);
        for (int i = length - 1; i < length * 2 - 1; i++) {
            l[i] = i - length + 1;
            r[i] = min(i - length + 2, v.size());
        }
        for (int i = length - 2; 0 <= i; i--) {
            l[i] = l[i * 2 + 1];
            r[i] = r[i * 2 + 2];
        }
    };
};
/* main */
signed main() {
    ll N, Q;
    cin >> N >> Q;
    vector<pi> a(N);
    FOR(i, 0, N) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    auto f = [](pi a, pi b) {
        return min(a, b);
    };
    SegmentTree<pi> st(a, f, make_pair(INF, INF));
    FOR(q, 0, Q) {
        int query, l, r;
        cin >> query;
        if (query == 1) {
            cin >> l >> r;
            l--;
            r--;
            int pre_l = st.query(l, l + 1).first;
            int pre_r = st.query(r, r + 1).first;
            st.change(l, make_pair(pre_r, l + 1));
            st.change(r, make_pair(pre_l, r + 1));
        }
        if (query == 2) {
            cin >> l >> r;
            l--;
            r--;
            cout << st.query(l, r + 1).second << endl;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0