結果

問題 No.875 Range Mindex Query
ユーザー hsyhsy
提出日時 2024-06-11 20:17:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 10,205 bytes
コンパイル時間 12,484 ms
コンパイル使用メモリ 616,452 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-11 20:17:44
合計ジャッジ時間 13,479 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 48 ms
6,944 KB
testcase_12 AC 39 ms
6,940 KB
testcase_13 AC 31 ms
6,940 KB
testcase_14 AC 31 ms
6,944 KB
testcase_15 AC 41 ms
6,944 KB
testcase_16 AC 48 ms
6,940 KB
testcase_17 AC 50 ms
6,940 KB
testcase_18 AC 49 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp__=boost::multiprecision;
using bint=mp__::cpp_int;
using greatd=mp__::number<mp__::cpp_dec_float<1024>>;
using namespace std;
template<class T=int> using V=vector<T>;
template<class T=int> using VV=V<V<T>>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pli=pair<ll,int>;
using pil=pair<int,ll>;
using pdd=pair<ld,ld>;
using vi=vector<int>;
using vvi=V<vi>;
using vpi=vector<pii>;
using vvpi=V<vpi>;
using vl=vector<ll>;
using vvl=V<vl>;
using vs=vector<string>;
using vvs=V<vs>;
using vc=vector<char>;
using vvc=V<vc>;
using vd=vector<ld>;
using vvd=V<vd>;
using vpl=vector<pll>;
using vvpl=V<vpl>;
using vpil=vector<pair<int,ll>>;
using vvpil=V<vpil>;
using vpli=vector<pair<ll,int>>;
using vvpli=V<vpli>;
using vpd=vector<pdd>;
using vvpd=V<vpd>;
using vb=vector<bool>;
using vvb=V<vb>;
template<class T> using pq=priority_queue<T,vector<T>,greater<T>>;
template<class T> using rpq=priority_queue<T,vector<T>>;
template<class T,class U>ostream &operator<<(ostream &os,const pair<T,U> &p){os <<p.first <<" " <<p.second;return os;}
template<class T,class U>istream &operator>>(istream &is,pair<T,U> &p){is >>p.first >>p.second;return is;}
#define ovl4(a,b,c,d,name,...) name
#define rep1(n) for(int i=0; i<n; ++i)
#define rep2(i,n) for(int i=0; i<n; ++i)
#define rep3(i,a,b) for(int i=a; i<b; ++i)
#define rep4(i,a,b,c) for(int i=a; i<b; i+=c)
#define rep(...) ovl4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(a) for(int i=int(a)-1; i>=0; --i)
#define rrep2(i,a) for(int i=int(a)-1; i>=0; --i)
#define rrep3(i,a,b) for(int i=int(a)-1; i>=b; --i)
#define rrep4(i,a,b,c) for(int i=int(a)-1; i>=b; i-=c)
#define rrep(...) ovl4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define atrep(i,v) for(auto i:v)
void in(){}
template<class... T>void in(T&... a){(cin >>... >>a);}
template<class T>
void vin(vector<T> &v,int n=-1,int s=0){if(n==-1)n=v.size();rep(i,s,s+n)in(v[i]);}
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
void VIN(){}
template<class T,class... Ts>
void VIN(int ind,vector<T>& v,Ts&... vs){vin<T>(v,v.size()-ind,ind);if constexpr(sizeof...(vs)>0)VIN(ind,vs...);}
template<class T,class... Ts>
bool chmax(T &a,Ts... b){T c=a;for(auto i:{b...})a=max(a,i);return a==c;}
template<class T,class...Ts>
bool chmin(T &a,Ts... b){T c=a;for(auto i:{b...})a=min(a,i);return a==c;}
template<class T,class... Ts>
bool chcomp(function<T(T,T)> comp,T &a,Ts... b){T c=a;for(auto i:{b...})a=comp(a,i);return a==c;}
void print(){cout<<"\n";}
template<class T,class... Ts>
void print(const T &a,const Ts&... b){cout <<a;(cout<<... <<(cout<<" ",b));cout<<"\n";}
template<class T>
void vprint(vector<T> &v,bool ind1=false,string aid=" "){rep(i,(int)ind1,v.size()){if(i>(int)ind1){cout <<aid;}cout <<v[i];}print();}
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Sort(a) sort(all(a))
#define rsort(a) sort(rall(a))
#define Uniq(a) a.erase(unique(all(a)),a.end())
#define Rvs(a) reverse(all(a))
#define pb push_back
#define eb emplace_back
#define elif else if
#define cY cout <<"Yes\n"
#define cN cout <<"No\n"
void yn(bool b){if(b){cY;}else{cN;}}
void YN(bool b){if(b)cout <<"YES\n";else cout <<"NO\n";}
#define ft first
#define sd second
#define inr(l,x,r) (l<=x && x<=r)
#define hinr(l,x,r) (l<=x && x<r)
#define ingrid(i,a,b,h,w) (inr(i,a,h+i-1) && inr(i,b,w+i-1))
#define FIX cout <<fixed <<setprecision(15)
template<class T>
bool eql(const T &a){return true;};
template<class T,class... Ts>
bool eql(const T& a,const Ts&... b){bool ret=true;for(auto i:{b...})ret&=(i==a);return ret;}
bool operator==(const string& a,const string& b){return a.compare(b)==0;}
random_device rd;
mt19937 mt(rd());
const int INF=1e9;
const ll LINF=1e18;
const ll MOD=1e9+7;
const ll MMOD=998244353;
const ld eps=1e-10;
const ld PI=M_PI;
bool deql(const ld &a){return true;}
template<typename... Args>
bool deql(const ld& a,const Args&... b){bool ret=true;for(auto i:{b...})ret&=(inr(-eps,i-a,eps));return ret;}
int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
class xorshift{
    private:uint64_t x;
    public:
    xorshift(){mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());x=rnd();for(int i=0; i<100; i++)random();}
    uint64_t random(){x=x^(x<<7);return x=x^(x>>9);}
};xorshift rnd;

template<class T,auto op,auto e>
class segmenttree{
    private:
    std::vector<T> dat;
    int size,n;
    public:
	segmenttree():segmenttree(0){}
    explicit segmenttree(int n_):segmenttree(std::vector<T>(n_,e())){}
	explicit segmenttree(int n_,T init):segmenttree(std::vector<T>(n_,init)){}
    explicit segmenttree(const std::vector<T>& v):n(int(v.size())){
        size=1;
        while(size<v.size())size<<=1;
        dat.assign(size<<1,e());
        for(int i=0; i<n; ++i)dat[size+i]=v[i];
        for(int i=size-1; i>=1; --i)dat[i]=op(dat[i<<1],dat[i<<1|1]);
    }
	void set(int pos,T x){
        pos+=size;
        dat[pos]=x;
        while(pos>1){
			pos>>=1;
			dat[pos]=op(dat[pos<<1],dat[pos<<1|1]);
		}
    }
	void add(int pos,T x){
		pos+=size;
		dat[pos]+=x;
		while(pos>1){
			pos>>=1;
			dat[pos]=op(dat[pos<<1],dat[pos<<1|1]);
		}
	}
    T prod(int l,int r)const{
        T resl=e(),resr=e();
        l+=size;
        r+=size;
        while(l<r){
            if(l&1)resl=op(resl,dat[l++]);
            if(r&1)resr=op(dat[--r],resr);
            l>>=1;
            r>>=1;
        }
        return op(resl,resr);
    }
	T get(int pos)const{return dat[pos+size];}
	T operator[](int pos)const{return dat[pos+size];}
	T all_prod()const{return dat[1];}
	int max_right(int l,auto f)const{
		if(l==n)return n;
		l+=size;
		T t=e();
		do{
			while(l&1==0)l>>=1;
			if(!f(op(t,dat[l]))){
				while(l<size){
					l<<=1;
					if(f(op(t,dat[l]))){
						t=op(t,dat[l]);
						l++;
					}
				}
				return l-size;
			}
			t=op(t,dat[l]);
			l++;
		}while((l&-l)!=l);
		return n;
	}
	int min_left(int r,auto f)const{
		if(r==0)return 0;
		r+=size;
		T t=e();
		do{
			r--;
			while(r>1 && (r&1)==0)r>>=1;
			if(!f(op(dat[r],t))){
				while(r<size){
					r=r<<1|1;
					if(f(op(dat[r],t))){
						t=op(dat[r],t);
						r--;
					}
				}
				return r-size+1;
			}
			t=op(dat[r],t);
		}while((r&-r)!=r);
		return 0;
	}
};
template<class T,auto op,auto e,class F,auto mapping,auto composition,auto id>
class lazysegtree{
	private:
	int size,n,log;
	std::vector<T> dat;
	std::vector<F> lazy;
	void all_apply(int pos,F f){
		dat[pos]=mapping(f,dat[pos]);
		if(pos<size)lazy[pos]=composition(f,lazy[pos]);
	}
	void push(int pos){
		all_apply(pos<<1,lazy[pos]);
		all_apply(pos<<1|1,lazy[pos]);
		lazy[pos]=id();
	}
	void update(int pos){dat[pos]=op(dat[pos<<1],dat[pos<<1|1]);}
	public:
	lazysegtree():lazysegtree(0){}
	explicit lazysegtree(int n_):lazysegtree(std::vector<T>(n_,e())){}
	explicit lazysegtree(int n_,T init):lazysegtree(std::vector<T>(n_,init)){}
	explicit lazysegtree(const std::vector<T>& v):n(int(v.size())){
		size=1;
		while(size<n)size<<=1;
		int c=size;
		log=0;
		while((c&1)==0)log++,c>>=1;
		dat.assign(size<<1,e());
		lazy.assign(size<<1,id());
		for(int i=0; i<n; ++i)dat[size+i]=v[i];
		for(int i=size-1; i>=1; --i)update(i);
	}
	void set(int pos,T x){
		pos+=size;
		for(int i=log; i>=1; --i)push(pos>>i);
		dat[pos]=x;
		for(int i=1; i<=log; ++i)update(pos>>i);
	}
	T get(int pos){
		pos+=size;
		for(int i=log; i>=1; --i)push(pos>>i);
		return dat[pos];
	}
	T prod(int l,int r){
		if(l==r)return e();
		l+=size;
		r+=size;
		for(int i=log; i>=1; --i){
			if(((l>>i)<<i)!=l)push(l>>i);
			if(((r>>i)<<i)!=r)push((r-1)>>i);
		}
		T resl=e(),resr=e();
		while(l<r){
			if(l&1)resl=op(resl,dat[l++]);
			if(r&1)resr=op(dat[--r],resr);
			l>>=1;
			r>>=1;
		}
		return op(resl,resr);
	}
	T all_prod(){return dat[1];}
	void apply(int pos,F f){
		pos+=size;
		for(int i=log; i>=1; --i)push(pos>>i);
		dat[pos]=mapping(f,dat[pos]);
		for(int i=1; i<=log; ++i)update(pos>>i);
	}
	void apply(int l,int r,F f){
		if(l==r)return;
		l+=size;
		r+=size;
		for(int i=log; i>=1; --i){
			if(((l>>i)<<i)!=l)push(l>>i);
			if(((r>>i)<<i)!=r)push((r-1)>>i);
		}
		{
			int l2=l,r2=r;
			while(l<r){
				if(l&1)all_apply(l++,f);
				if(r&1)all_apply(--r,f);
				l>>=1;
				r>>=1;
			}
			l=l2,r=r2;
		}
		for(int i=1; i<=log; ++i){
			if(((l>>i)<<i)!=l)update(l>>i);
			if(((r>>i)<<i)!=r)update((r-1)>>i);
		}
	}
	int max_right(int l,auto g){
		if(l==n)return n;
		l+=size;
		for(int i=log; i>=1; --i)push(l>>i);
		T t=e();
		do{
			while((l&1)==0)l>>=1;
			if(!g(op(t,dat[l]))){
				while(l<size){
					push(l);
					l<<=1;
					if(g(op(t,dat[l]))){
						t=op(t,dat[l]);
						l++;
					}
				}
				return l-size;
			}
			t=op(t,dat[l]);
			l++;
		}while((l&-l)!=l);
		return n;
	}
	int min_left(int r,auto g){
		if(r==0)return 0;
		r+=size;
		for(int i=log; i>=1; --i)push((r-1)>>i);
		T t=e();
		do{
			r--;
			while(r>1 && (r&1)==0)r>>=1;
			if(!g(op(dat[r],t))){
				while(r<size){
					push(r);
					r=r<<1|1;
					if(g(op(dat[r],t))){
						t=op(dat[r],t);
						r--;
					}
				}
				return r-size+1;
			}
			t=op(dat[r],t);
		}while((r&-r)!=r);
		return 0;
	}
};
int op(int a,int b){return min(a,b);}
int e(){return numeric_limits<int>::max();}
int main(){
    ios::sync_with_stdio(false);std::cin.tie(nullptr);cout.tie(nullptr);FIX;
    INT(n,q);
    vi a(n);
    vin(a);
    segmenttree<int,op,e> sg(a);
    vector<int> index(n+1);
    rep(i,n)index[a[i]]=i+1;
    while(q--){
        INT(t,l,r);
        --l;
        if(t==1){
            --r;
            int lef=sg[l],rig=sg[r];
            sg.set(l,rig),sg.set(r,lef);
            swap(index[lef],index[rig]);
        }
        if(t==2)print(index[sg.prod(l,r)]);
    }
    return 0;
}
0