結果

問題 No.875 Range Mindex Query
ユーザー alexara1123alexara1123
提出日時 2019-09-06 22:13:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,420 bytes
コンパイル時間 1,102 ms
コンパイル使用メモリ 89,696 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 18:37:52
合計ジャッジ時間 2,964 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

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);
   for (int i = 0; i < n; i++)
   {
      cin >> a[i];
      seg.set(i, a[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);
         swap(a[l], a[r]);
      }
      else
      {
         cout << seg.get(l, r) + 1<< endl;
      }
   }
}
0