結果

問題 No.875 Range Mindex Query
ユーザー snrnsidy
提出日時 2021-03-05 07:36:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 2,790 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 119,284 KB
最終ジャッジ日時 2025-01-19 10:19:10
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <unordered_set>
#include <fstream>
using namespace std;
int tree[1 << 20];
int a[100001];
int init(int node, int start, int end)
{
    if (start == end)
    {
        return tree[node] = start;
    }
    int mid = (start + end) / 2;
    int l = init(2 * node, start, mid);
    int r = init(2 * node + 1, mid + 1, end);
    if (a[l] > a[r])
    {
        tree[node] = r;
    }
    else if (a[l] < a[r])
    {
        tree[node] = l;
    }
    else
    {
        tree[node] = min(l, r);
    }
    return tree[node];
}
void update(int node, int start, int end, int index)
{
    if (index < start || index > end)
    {
        return;
    }
    if (start == end)
    {
        tree[node] = start;
        return;
    }
    if (start != end)
    {
        int mid = (start + end) / 2;
        update(2 * node, start, mid, index);
        update(2 * node + 1, mid + 1, end, index);
    }
    int x = tree[2 * node];
    int y = tree[2 * node + 1];
    //cout << node << ' ' << start << ' ' << end << ' ' << tree[node] << '\n';
    //cout << 2*node << ' ' << start << ' ' << (start+end)/2 << ' ' << x <<  ' ' << a[x] << '\n';
    //cout << 2*node+1 << ' ' << (start+end)/2 + 1 << ' ' << end << ' ' << y << ' ' << a[y] << '\n'; 
    if (a[x] < a[y])
    {
        tree[node] = x;
    }
    else if (a[x] > a[y])
    {
        tree[node] = y;
    }
    else
    {
        tree[node] = min(x, y);
    }
}
int find(int node, int start, int end, int left, int right)
{
    if (right < start || end < left)
    {
        return 0;
    }
    if (left <= start && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end) / 2;
    int x = find(2 * node, start, mid, left, right);
    int y = find(2 * node + 1, mid + 1, end, left, right);
    //cout << node << ' ' << start << ' ' << end << ' ' << tree[node] << '\n';
    //cout << 2*node << ' ' << start << ' ' << (start+end)/2 << ' ' << x <<  ' ' << a[x] << '\n';
    //cout << 2*node+1 << ' ' << (start+end)/2 + 1 << ' ' << end << ' ' << y << ' ' << a[y] << '\n'; 
    if (a[x] < a[y])
    {
        return x;
    }
    else if (a[x] > a[y])
    {
        return y;
    }
    return min(x, y);
}
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, x, y, z;
    cin >> n >> m;
    for (int i = 0; i <= 100000; i++)
    {
        a[i] = 2e9;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    init(1, 0, n);
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        if (x == 1)
        {
            int tmpa = a[y];
            int tmpb = a[z];
            a[y] = tmpb;
            a[z] = tmpa;
            update(1, 0, n, y);
            update(1, 0, n, z);
            //init(1,0,n);
        }
        else
        {
            cout << find(1, 0, n, y, z) << '\n';
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0