#include #include #include #include #include #include #include #include #include #include typedef char SINT8; typedef short SINT16; typedef int SINT32; typedef long long SINT64; typedef double DOUBLE; #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define ABS(a) ((a)>(0)?(a):-(a)) #define rep(i,a,b) for(SINT64 (i)=SINT64(a);(i)=SINT64(b);(i)--) #define put(a) cout << (a) << endl #define puts(a) cout << (a) << " " #define INF 1000000001 #define MOD 1000000007 #define INF64 1000000000000000001 #define F first #define S second #define Pii pair #define Pll pair #define Piii pair> #define Plll pair> #define Vll(a,b,c) vector> (a)((b),vector((c)) #define Vlll(a,b,c,d) vector>> (a)((b),vector>((c),vector((d))) using namespace std; class SegTree { private: SINT64 size; vector node; vector segdata; SINT64 jugdement(SINT64 a, SINT64 b) { SINT64 ans = 0; ans = min(a,b); return ans; } public: //コンストラクタ SegTree(vector data) { SINT64 ori_size; ori_size = data.size(); size = 1; while (size < ori_size) { size *= 2; } node.resize(2*size-1, INF); segdata.resize(ori_size,INF); rep(i,0,ori_size) { node[size-1+i] = i; node[size-1+i] = i; node[size-1+i] = i; node[size-1+i] = i; node[size-1+i] = i; segdata[i] = data[i]; } rrep(i,size-2,0) { if ((node[2*i+1] != INF) && (node[2*i+2] != INF)) { if (segdata[node[2*i+1]] > segdata[node[2*i+2]]) { node[i] = node[2*i+2]; } else { node[i] = node[2*i+1]; } } else if ((node[2*i+1] == INF) && (node[2*i+2] == INF)) { node[i] = INF; } else if (node[2*i+1] == INF) { node[i] = node[2*i+2]; } else { node[i] = node[2*i+1]; } } } //データ更新 void update(SINT64 x, SINT64 val) { segdata[x] = val; x += (size - 1); while(x > 0) { x = (x - 1) / 2; if ((node[2*x+1] != INF) && (node[2*x+2] != INF)) { if (segdata[node[2*x+1]] > segdata[node[2*x+2]]) { node[x] = node[2*x+2]; } else { node[x] = node[2*x+1]; } } else if ((node[2*x+1] == INF) && (node[2*x+2] == INF)) { node[x] = INF; } else if (node[2*x+1] == INF) { node[x] = node[2*x+2]; } else { node[x] = node[2*x+1]; } } } //データ取得 [a,b) SINT64 getdata(SINT64 a, SINT64 b, SINT64 k = 0, SINT64 l = 0, SINT64 r = -1) { if (r < 0) { r = size; } //要求範囲外 if ((r <= a) || (b <= l)) { return INF; } //完全要求区間内 if ((a <= l) && (r <= b)) { return node[k]; } SINT64 vl = getdata(a, b, 2*k+1, l, (l+r)/2); SINT64 vr = getdata(a, b, 2*k+2, (l+r)/2, r); if ((vl != INF) && (vr != INF)) { if (segdata[node[vl]] > segdata[node[vr]]) { return node[vr]; } else { return node[vl]; } } else if ((vl == INF) && (vr == INF)) { return INF; } else if (vl == INF) { return node[vr]; } else { return node[vl]; } } //取得 SINT64 getnode(SINT64 x) { return segdata[x]; } //表示 void disp() { rep(i,0,size) { puts(segdata[i]); } cout << endl; } void alldisp() { SINT64 cnt = 0; SINT64 end = 2; while (1) { puts(node[cnt]); if (cnt == end-2) { end *= 2; cout << endl; } cnt++; if (cnt == size*2-1) { break; } } } }; int main() { SINT64 N; cin >> N; SINT64 Q; cin >> Q; vector data(N); rep(i,0,N) { cin >> data[i]; } SegTree seg(data); rep(i,0,Q) { SINT64 a,b,c; cin >> a >> b >> c; b--, c--; if (a == 1) { SINT64 buf = seg.getnode(b); seg.update(b,seg.getnode(c)); seg.update(c,buf); } else { put( seg.getdata(b,c+1) + 1); } } return 0; } // vector> data(N,vector(3)); //2次元配列 // vector>> data(N,vector>(3,vector(3))); //3次元配列 // Vll(data,N,N); //2次元配列 // Vlll(data,N,N,N); //3次元配列 // sort(data.begin(),data.end()); // sort(data.begin(),data.end(),std::greater()); // __gcd(A,B); /* 複数条件ソート bool sortcompare(Pll A, Pll B) { if(A.F == B.F){ return A.S > B.S; } else { return A.F < B.F; } } sort(data.begin(),data.end(),sortcompare); */ // タプル //vector> edges; //edges.emplace_back(a,b,c); //cout << get<0>(edges[i]); //cout << get<1>(edges[i]); //cout << get<2>(edges[i]); // data.emplace_back(BUF); //後ろに追加 // data.erase(std::unique(data.begin(), data.end()), data.end()); //ソート後に使用 同じ値を消す // data.insert(data.begin() + X, 0); //X番目の要素に0を挿入 // 隣接リスト // vector> data(N); // data[ A ].emplace_back( B ); /* vector data(N); rep(i,0,N) { cin >> data[i].F; cin >> data[i].S; } sort(data.begin(),data.end()); */ /* vector data(N); rep(i,0,N) { cin >> data[i].F; cin >> data[i].S.F; cin >> data[i].S.S; } sort(data.begin(),data.end()); */ // lower_boundは値がなければ最大値(.size())を返す // posi = lower_bound(data.begin(),data.end(), X) - data.begin(); // X以上を探す // posi = lower_bound(data.begin(),data.end(),make_pair(X,0)) - data.begin(); //pair /* 文字列回転 string N; cin >> N; N = N[N.length()-1] + N.substr(0,N.length()-1); s = to_string(i); //ストリング変換 */ /* 文字列合成 string N,M; cin >> N >> M; SINT64 ans = 0; ans = stoi(N+M); */ /* //ワーシャルフロイド vector> dist(N,vector(N)); rep(i,0,N) { rep(j,0,N) { if (i != j) { dist[i][j] = INF; } } } rep(k,0,N) { rep(i,0,N) { rep(j,0,N) { dist[i][j] = MIN(dist[i][j], dist[i][k]+dist[k][j]); } } } */ /* 優先度付きキュー priority_queue, greater> bufq; //小さいほうから取り出せる priority_queue> bufq; //大きいほうから取り出せる bufq.push(X); //X を挿入 bufq.top(); //先頭データ読み bufq.pop(); //先頭データ削除 */ /* キュー queue bufq; //宣言 bufq.push(0); //挿入 bufq.front(); //先頭データ読み bufq.pop(); //先頭データ削除 */ /* SET コンテナ set data; data.insert(X); //X を挿入 data.erase(data.begin()); //先頭を削除 data.erase(--data.end()); //末尾を削除 *data.begin(); //先頭要素にアクセス *data.rbegin(); //末尾要素にアクセス //全表示 set::iterator it; //イテレータを用意 for(it = data.begin(); it != data.end(); it++) { cout << *it << " "; } cout << endl; //N番目を一部表示 set::iterator it; // イテレータを用意 it = data.begin(); rep (i,0,N) { it++; } cout << *it << endl; */ /* map map mp; SINT32 N = 0; SINT32 mx = 0; cin >> N; for (SINT32 i = 0; i < N; i++) { string s; cin >> s; mp[s]++; } for(auto it=mp.begin();it!=mp.end();it++) { mx=max(mx,it->second); } */ /* //順列全表示 //sortしてからでないと全列挙にならない sort(data.begin(),data.end()); do { cout << buf << endl; rep(i,0,R) { cout << data[i] << " "; } cout << endl; } while (next_permutation(data.begin(),data.end())); */ // 桁指定表示 // ans = ans * M_PI; // cout << setprecision(15) << ans << endl; // 逆元 コンビネーション /* SINT64 modpow(SINT64 a, SINT64 p) { if (p == 0) return 1; if (p % 2 == 0) { //pが偶数の時 SINT64 halfP = p / 2; SINT64 half = modpow(a, halfP); //a^(p/2) をhalfとして、half*halfを計算 return half * half % MOD; } else { //pが奇数の時は、偶数にするために1減らす return a * modpow(a, p - 1) % MOD; } } SINT64 calcComb(SINT64 a, SINT64 b) { SINT64 Mul = 1; SINT64 Div = 1; SINT64 ans = 0; if (b > a - b) { return calcComb(a, a - b); } rep(i,0,b) { Mul *= (a - i); Div *= (i + 1); Mul %= MOD; Div %= MOD; } ans = Mul * modpow(Div, MOD - 2) % MOD; return ans; } */ /* UNION FIND class UnionFind { public: vector parent; UnionFind(SINT64 N) { parent = vector(N+10, -1); //少し多めに } SINT64 root(SINT64 A) { if (parent[A] < 0) { return A; } else { parent[A] = root(parent[A]); return parent[A]; } } SINT64 size(SINT64 A) { return parent[root(A)] * (-1); } bool judge(SINT64 A, SINT64 B) { A = root(A); B = root(B); if (A == B) { return true; //同じグループ } else { return false; //違うグループ } } void connect(SINT64 A, SINT64 B) { A = root(A); B = root(B); if (A != B) { if (size(A) < size(B)) { swap(A, B); } parent[A] += parent[B]; parent[B] = A; } } }; UnionFind uni(N); */ /* class SegTree { private: SINT64 size; vector node; SINT64 jugdement(SINT64 a, SINT64 b) { SINT64 ans = 0; ans = a+b; return ans; } public: //コンストラクタ SegTree(vector data) { SINT64 ori_size; ori_size = data.size(); size = 1; while (size < ori_size) { size *= 2; } node.resize(2*size-1, 0); rep(i,0,ori_size) { node[size-1+i] = data[i]; } rrep(i,size-2,0) { node[i] = jugdement(node[2*i+1], node[2*i+2]); } } //データ更新 void update(SINT64 x, SINT64 val) { x += (size - 1); node[x] = val+node[x]; while(x > 0) { x = (x - 1) / 2; node[x] = jugdement(node[2*x+1], node[2*x+2]); } } //データ取得 [a,b) SINT64 getdata(SINT64 a, SINT64 b, SINT64 k = 0, SINT64 l = 0, SINT64 r = -1) { if (r < 0) { r = size; } //要求範囲外 if ((r <= a) || (b <= l)) { return 0; } //完全要求区間内 if ((a <= l) && (r <= b)) { return node[k]; } SINT64 vl = getdata(a, b, 2*k+1, l, (l+r)/2); SINT64 vr = getdata(a, b, 2*k+2, (l+r)/2, r); return jugdement(vl, vr); } //表示 void disp() { rep(i,0,size) { puts(node[size-1+i]); } cout << endl; } void alldisp() { SINT64 cnt = 0; SINT64 end = 2; while (1) { puts(node[cnt]); if (cnt == end-2) { end *= 2; cout << endl; } cnt++; if (cnt == size*2-1) { break; } } } }; SegTree seg(N); */