結果

問題 No.875 Range Mindex Query
ユーザー nu50218nu50218
提出日時 2019-09-08 22:40:25
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 223 ms
7,808 KB
testcase_12 AC 180 ms
5,760 KB
testcase_13 AC 145 ms
7,936 KB
testcase_14 AC 143 ms
8,064 KB
testcase_15 AC 201 ms
8,064 KB
testcase_16 AC 249 ms
8,064 KB
testcase_17 AC 271 ms
8,064 KB
testcase_18 AC 255 ms
8,064 KB
権限があれば一括ダウンロードができます

ソースコード

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;
        }
    }
}
0