結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー haji149
提出日時 2019-09-06 22:04:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 338 ms / 2,000 ms
コード長 6,377 bytes
コンパイル時間 2,310 ms
コンパイル使用メモリ 187,252 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-06-24 17:56:39
合計ジャッジ時間 5,688 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

template<typename T>
class Array{
public:
  struct Node{
    T val;
    T mn;
    int priority;
    int size;
    Node *parent, *left, *right;

    void refresh(){
      size = 1;
      mn = val;
      if(left != nullptr) {
        left->parent = this;
        size += left->size;
        mn = min(mn, left->mn);
      }
      if(right != nullptr) {
        right->parent = this;
        size += right->size;
        mn = min(mn, right->mn);
      }
    }

    Node():val(T()), priority(-1), parent(nullptr), left(nullptr), right(nullptr){refresh();};
    Node(const T &val,int priority,Node *parent):
      val(val), priority(priority), parent(parent), left(nullptr), right(nullptr){refresh();};

    Node(const T &val,int priority, Node *parent,Node *left,Node *right):
      val(val), priority(priority), parent(parent), left(left), right(right){refresh();};
  };

  mt19937 mt; //[0, 2^32]までのpriorityを決める乱数生成機
  Node *root;
  T INF;
  Array(T INF):mt((unsigned int) time(NULL)), root(nullptr), INF(INF){}

  int size(){return size(root);}
  int size(Node *t){return t == nullptr? 0:t->size;}
  int empty(){return size(root) == 0;}

  Node* rightRotate(Node *y){
    Node *x = y->left;
    y->left = x->right;
    x->right = y;

    x->parent = y->parent;
    y->parent = x;

    y->refresh(), x->refresh();
    return x;
  }

  Node* leftRotate(Node *x){
    Node *y = x->right;
    x->right = y->left;
    y->left = x;

    y->parent = x->parent;
    x->parent = y;

    x->refresh(), y->refresh();
    return y;
  }

  Node* insert(Node *t,int k, T val,int priority, Node *parent = nullptr){
    if(t == nullptr) return new Node(val, priority, parent);

    if(size(t->left) >= k){
      t->left = insert(t->left, k, val, priority,  t);
      if( t->priority < t->left->priority ) t = rightRotate(t);
    }
    else{
      t->right = insert(t->right, k - size(t->left) - 1, val, priority, t);
      if( t->priority < t->right->priority ) t = leftRotate(t);
    }
    t->refresh();
    return t;
  }

  //k番目の位置にvalを挿入
  void insert(int k, T val){
    assert(0 <= k && k <= size());
    int priority = mt(); //[-2^31, 2^31 - 1]
    root = insert(root, k, val, priority);
  }

  void push_back(T val){return insert(size(), val);}
  void push_front(T val){return insert(0, val);}

  Node* erase(Node *t,int k){
    if(size(t->left) + 1 == k+1) return _erase(t, k);
    if(k <= size(t->left)) t->left = erase(t->left, k);
    else t->right = erase(t->right, k - size(t->left) - 1);
    t->refresh();
    return t;
  }

  Node* _erase(Node *t,int k){
    if(t->left == nullptr && t->right == nullptr) {
      delete t;
      return nullptr;
    }
    if(t->left == nullptr) t = leftRotate(t);
    else if(t->right == nullptr) t = rightRotate(t);
    else {
      if( t->left->priority > t->right->priority ) t = rightRotate(t);
      else t = leftRotate(t);
    }
    t->refresh();
    return erase(t, k);
  }

  void erase(int k){assert(0 <= k && k < size()); root = erase(root, k);}
  void pop_front(){root = erase(0);}
  void pop_back(){root = erase(size()-1);}

  Node* getKthNode(Node *t, int k){
    if(size(t->left)+1 == k) return t;
    if(size(t->left) >= k) return getKthNode(t->left, k);
    return getKthNode(t->right, k - size(t->left) - 1);
  }

  T& operator[](int i){
    assert(i < size());
    return getKthNode(root, i+1)->val;
  }

  friend ostream& operator << (ostream& os,Array<T> &a){
    for(int i=0;i<a.size();i++){
      if(i) os<<" ";
      os<<a[i];
    }
    os<<endl;
    return os;
  }

  friend istream& operator >> (istream& is,Array<T> &a){
    for(int i=0;i<a.size();i++) is>>a[i];
    return is;
  }

  T argmin(Node *t, int a, int b, int l, int r){
    if(t == nullptr || r <= a || b <= l) return INF;
    if(a <= l && r <= b) return t->mn;
    assert(r - l == size(t));
    T lval = argmin(t->left, a, b, l, r  - size(t->right) - 1);
    T rval = argmin(t->right, a, b, l + size(t->left) + 1, r);

    int k = l + size(t->left);
    T res = min(lval, rval);
    if(a <= k && k < b) res = min(res, t->val);
    return res;
  }

  T argmin(int l, int r){return argmin(root, l, r, 0, size());}
};


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, Q;
  cin>>N>>Q;

  Array<P> T(P(INF, INF));
  vector<int> A(N);
  for(int i=0;i<N;i++) {
    cin>>A[i];
    T.insert(i, P(A[i], i));
  }

  while(Q--){
    int cmd, l, r;
    cin>>cmd>>l>>r; l--, r--;

    if(cmd == 1){
      T.erase(l);
      T.insert(l, P(A[r], l));

      T.erase(r);
      T.insert(r, P(A[l], r));
      swap(A[l], A[r]);
    }
    else{
      int ans = T.argmin(l, r+1).second;
      cout<<ans+1<<endl;
    }
  }
  return 0;
}
0