結果

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

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;
typedef long long ll;
ll MOD = 1000000007;
typedef pair<int, int> P;
#define INF 1e9

template <class Monoid>
struct SegTree
{
   using Func = function<Monoid(Monoid, Monoid)>;
   const Func F;
   const Monoid UNITY;
   int SIZE_R;
   vector<Monoid> dat;

   SegTree(int n, const Func f, const Monoid &unity) : F(f), UNITY(unity) { init(n); }
   void init(int n)
   {
      SIZE_R = 1;
      while (SIZE_R < n)
         SIZE_R *= 2;
      dat.assign(SIZE_R * 2, UNITY);
   }

   /* set, a is 0-indexed */
   void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
   void build()
   {
      for (int k = SIZE_R - 1; k > 0; --k)
         dat[k] = F(dat[k * 2], dat[k * 2 + 1]);
   }

   /* update a, a is 0-indexed */
   void update(int a, const Monoid &v)
   {
      int k = a + SIZE_R;
      dat[k] = v;
      while (k >>= 1)
         dat[k] = F(dat[k * 2], dat[k * 2 + 1]);
   }

   /* get [a, b), a and b are 0-indexed */
   Monoid get(int a, int b)
   {
      Monoid vleft = UNITY, vright = UNITY;
      for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1)
      {
         if (left & 1)
            vleft = F(vleft, dat[left++]);
         if (right & 1)
            vright = F(dat[--right], vright);
      }
      return F(vleft, vright);
   }
   inline Monoid operator[](int a) { return dat[a + SIZE_R]; }

   /* debug */
   void print()
   {
      for (int i = 0; i < SIZE_R; ++i)
      {
         cout << (*this)[i];
         if (i != SIZE_R - 1)
            cout << ",";
      }
      cout << endl;
   }
};

ll a[101010];
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);

   int n, q;
   cin >> n >> q;
   SegTree<int> seg(n, [](int a, int b) { return min(a, b); }, INF);
   map<int, int> m;
   for (int i = 0; i < n; i++)
   {
      cin >> a[i];
      seg.set(i, a[i]);
      m[a[i]] = i;
   }
   seg.build();

   for (int i = 0; i < q; i++)
   {
      int f, l, r;
      cin >> f >> l >> r;
      l--;
      r--;
      if (f == 1)
      {
         int ta = a[l], tb = a[r];
         seg.update(l, tb);
         seg.update(r, ta);
         m[ta] = r;
         m[tb] = l;
         a[l] = tb;
         a[r] = ta;
         //swap(a[l], a[r]);
      }
      else
      {
         // seg.print();
         // cout
         //     << seg.get(l, r) << endl;
         cout << m[seg.get(l, r + 1)] + 1 << endl;
      }
   }
}
0