結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー suzuken_w
提出日時 2020-02-07 15:16:26
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,867 bytes
記録
コンパイル時間 2,215 ms
コンパイル使用メモリ 186,016 KB
実行使用メモリ 13,136 KB
最終ジャッジ日時 2024-09-25 07:15:43
合計ジャッジ時間 4,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
// set:T,map:f  TxT→T =(T,f)
// set:E,map:h ExE→E =(E,h)
//map: g:TxE→T
//1-index
template<typename T,typename E>
struct lazysegtree{
using F=function<T(T,T)>;
using G=function<T(T,E)>;
using H=function<E(E,E)>;
int n,height;
F f;G g;H h;T t;E e;
vector<T> dat;
vector<E> laz;
lazysegtree(int n_,F f,G g,H h,T t,E e):f(f),g(g),h(h),t(t),e(e){
    n=1;height=0;
    while(n<n_)n*=2,height++;
    dat.assign(2*n,t);
    laz.assign(2*n,e);
}
lazysegtree(int n_,vector<T> &v,F f,G g,H h,T t,E e):f(f),g(g),h(h),t(t),e(e){
    n=1;height=0;
    while(n<n_)n*=2,height++;
    dat.assign(2*n,t);
    for(int i=n;i<n+v.size();i++)dat[i]=v[i-n];
    for(int i=n-1;i>0;i--)dat[i]=f(dat[i*2+1],dat[i*2+2]);
    laz.assign(2*n,e);
}
inline T reflect(int k){
    return (laz[k]==e?dat[k]:g(dat[k],laz[k]));
}
inline void eval(int k){
    if(laz[k]==e)return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=e;
}
inline void thrust(int k){
    for(int i=height;i>0;i--)eval(k>>i);
}
inline void recalc(int k){
    while(k>>=1)dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
}
void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
        if(l&1)laz[l]=h(laz[l],x),l++;
        if(r&1)--r,laz[r]=h(laz[r],x);
    }
recalc(a);
recalc(b);
}
void setval(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=e;
    recalc(a);
}
T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=t,vr=t;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
        if(l&1)vl=f(vl,reflect(l++));
        if(r&1)vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
}
};
int main(){
ll n,q;
cin>>n>>q;
auto f=[](P a,P  b){return min(a,b);};
V<P> dat(n);
for(int i=0;i<n;i++){
    cin>>dat[i].fi;
    dat[i].se=i+1;
}
lazysegtree<P,P> tree(n,dat,f,f,f,{INT_MAX,INT_MAX},{INT_MAX,0});
int c;
while(q--){
    cin>>c;
    if(c==2){
        int s,t;
        cin>>s>>t;
        s--;t--;
        cout<<tree.query(s,t+1).se<<endl;
    }
    else{
        int s,t;
        cin>>s>>t;
        s--;t--;
        P l=tree.query(s,s+1);
        P r=tree.query(t,t+1);
        swap(l.se,r.se);
        tree.setval(s,r);
        tree.setval(t,l);
    }
}
}
0