結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー frmon60
提出日時 2019-09-21 15:20:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 2,106 bytes
コンパイル時間 2,503 ms
コンパイル使用メモリ 191,636 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 23:32:08
合計ジャッジ時間 3,980 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) v.begin(),v.end()
#define Pr(type) priority_queue<type>
#define gPr(type) priority_queue<type,vector<type>,greater<type>>
#define V(type) vector<type>
#define rep(i,n) for(int i=0; i<n; i++)
#define rer(i,st,en) for(int i=st; i<en; i++)
#define gnr(i,l,r) for(int i=int(r)-1; i>=int(l); i--)
#define eb emplace_back
#define pri1(a) cout<<a<<'\n'
#define pri2(a,n) rep(i,n)cout<<a[i]<<'\n'
#define pri3(a,n) rep(i,n-1)cout<<a[i]<<' '; cout<<a[n-1]<<'\n'
#define prip(p) cout<<p.first<<' '<<p.second<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class T,class F>
struct SegTree{
	V(T) buf;
	int s;
	const F f;
	const T g;
	SegTree(const V(T)& d,F ff,T gg):f(ff),g(gg){
		int n=d.size();
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,g);
		rep(i,n)
			buf[i+s]=d[i];
		gnr(i,1,s)
			u(i);
	}
	void u(int i){
		buf[i]=f(buf[i*2],buf[i*2+1]);
	}
	void set(int i,T t){
		i+=s;
		buf[i]=t;
		while(i>>=1)u(i);
	}
	T get(int b,int e,int l,int r,int i){
		if(e<=l||r<=b)return g;
		if(b<=l&&r<=e)return buf[i];
		int m=(l+r)/2;
		return f(get(b,e,l,m,i*2),get(b,e,m,r,i*2+1));
	}
	T get(int b,int e){
		return get(b,e,0,s,1);
	}
  T operator[](const int &k)const{
    return buf[k+s];
  }
};
template<class T,class F>
SegTree<T,F> segtree(const V(T)& d,F f,T g){
	return SegTree<T,F>(d,f,g);
}

int n,m,_,x,y,q,key;
string s,sb;
bool ok;



int main(){
  cin.tie(nullptr); ios::sync_with_stdio(false);

  cin>>n>>q; V(P) a(n);
  rep(i,n){cin>>x; a[i]=P(x,i+1);}
  auto seg=segtree(a,[](P x,P y){return min(x,y);},P(1e6,1e6));
  //rep(i,n)prip(seg[i]);
  rep(i,q){
    cin>>m>>x>>y; x--;
    if(m==2)pri1(seg.get(x,y).second);
    else{y--; swap(a[x].first,a[y].first); seg.set(x,a[x]); seg.set(y,a[y]);}
  }
}
0