#490160 (C++17) No.875 Range Mindex Query

• 問題: No.875 Range Mindex Query
• ユーザー: fura
• 提出日時: 2020-06-01 03:55:30
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 1,073 bytes
• コンパイル時間: 2,580 ms
• コンパイル使用メモリ: 204,444 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-04-30 18:42:48
• 合計ジャッジ時間: 4,166 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	2 ms; 6,944 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	2 ms; 6,944 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	66 ms; 6,940 KB
testcase_12	AC	53 ms; 6,940 KB
testcase_13	AC	49 ms; 6,940 KB
testcase_14	AC	47 ms; 6,944 KB
testcase_15	AC	66 ms; 6,940 KB
testcase_16	AC	78 ms; 6,944 KB
testcase_17	AC	85 ms; 6,944 KB
testcase_18	AC	82 ms; 6,940 KB

ソースコード

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

class segment_tree{
	int n;
	vector<int> dat;
	int query(int l,int r,int a,int b,int u){
		if(l<=a && b<=r) return dat[u];
		int res=INF;
		int c=(a+b)/2;
		if(l<c && a<r) res=min(res,query(l,r,a,c,2*u+1));
		if(l<b && c<r) res=min(res,query(l,r,c,b,2*u+2));
		return res;
	}
public:
	segment_tree(int N){
		for(n=1;n<N;n*=2);
		dat.assign(2*n-1,0);
	}
	void update(int u,int val){
		u+=n-1;
		dat[u]=val;
		while(u>0) u=(u-1)/2, dat[u]=min(dat[2*u+1],dat[2*u+2]);
	}
	int query(int l,int r){ return query(l,r,0,n,0); }
};

int main(){
	int n,q; scanf("%d%d",&n,&q);
	vector<int> p(n),inv(n);
	rep(i,n){
		scanf("%d",&p[i]); p[i]--;
		inv[p[i]]=i;
	}

	segment_tree ST(n);
	rep(i,n) ST.update(i,p[i]);

	rep(_,q){
		int type,l,r; scanf("%d%d%d",&type,&l,&r);
		if(type==1){
			l--; r--;
			ST.update(l,p[r]);
			ST.update(r,p[l]);
			swap(inv[p[l]],inv[p[r]]);
			swap(p[l],p[r]);
		}
		else{
			l--;
			printf("%d\n",inv[ST.query(l,r)]+1);
		}
	}

	return 0;
}