UVa12299

UVa112299
蟻本からSegmentTreeを拝借。
更新を繰り返して間に合う。

// UVa 12299
#include <iostream>
#include <algorithm>

#include <climits>
#include <cstdio>
#include <cassert>

using namespace std;

const int N = 100000 + 1;

namespace SegTree {
  const int MAX_N = 1 << 17;
  int n, dat[2 * MAX_N - 1];
  
  void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;  
    fill(dat, dat + 2 * n - 1, INT_MAX);
  }

  // k-th = v (0 base index)  
  void update(int k, int v) {
    k += n - 1;
    dat[k] = v;
    while (0 < k) {
      k = (k - 1) / 2;
      dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
    return ;
  }

  int query_(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return INT_MAX;
    if (a <= l && r <= b) return dat[k];

    int vl = query_(a, b, k * 2 + 1, l, (l + r) / 2);
    int vr = query_(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }

  // returns min value in [a, b)
  inline
  int query(int a, int b) {
    return query_(a, b, 0, 0, n);
  }
}

int main(void) {

  static int num[N];
  const int B = 30 + 10;
  char buff[B];
  int idx[B];

  int n, q;
  while (scanf("%d%d\n", &n, &q) == 2) {

    SegTree::init(n);
    for (int i = 0; i < n; ++i) {      
      scanf("%d", num + i);
      SegTree::update(i, num[i]);
    }
    scanf("\n");

    while (q--) {
      gets(buff);
      char c = buff[0];

      int size = 0;
      fill(idx, idx + B, 0);
      for (int i = 0; i < B; ++i) {
        if (isdigit(buff[i])) {
          idx[size] = idx[size] * 10 + (buff[i] - '0');
        } else {
          if (idx[size]) {
            --idx[size];
            ++size;
          }
        }
        buff[i] = 0;
      }

      if (c == 's') {
        int tmp = num[idx[0]];
        for (int i = 0; i+1 < size; ++i) {
          int j = (i + 1) % size;
          num[idx[i]] = num[idx[j]];
        }
        num[idx[size - 1]] = tmp;
        for (int i = 0; i < size; ++i) {
          SegTree::update(idx[i], num[idx[i]]);
        }
      } else {        
        printf("%d\n", SegTree::query(idx[0], idx[1] + 1));
      }
    }
  }
  return 0;
}