結果

問題 No.875 Range Mindex Query
ユーザー alexara1123alexara1123
提出日時 2019-09-06 22:46:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 237 ms / 2,000 ms
コード長 2,633 bytes
コンパイル時間 1,020 ms
コンパイル使用メモリ 96,388 KB
実行使用メモリ 9,552 KB
最終ジャッジ日時 2023-09-07 01:39:45
合計ジャッジ時間 3,628 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 187 ms
8,344 KB
testcase_12 AC 159 ms
6,716 KB
testcase_13 AC 144 ms
9,088 KB
testcase_14 AC 141 ms
8,880 KB
testcase_15 AC 189 ms
9,432 KB
testcase_16 AC 212 ms
9,044 KB
testcase_17 AC 237 ms
9,552 KB
testcase_18 AC 225 ms
9,348 KB
権限があれば一括ダウンロードができます

ソースコード

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