Kyselyt

// C

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

template<typename T, int N, class CT, T inf>
class seqtree {
public:
  CT cmp;
  vector<T> tree;
  
  seqtree() : tree(2*N) {
    for (auto &v : tree)
      v = inf;
  }
  
  void set(int i, int v) {
    i += N;
    tree[i] = v;
    i /= 2;
    while (i > 0) {
      if (cmp(tree[2*i], tree[2*i+1]))
	tree[i] = tree[2*i];
      else
	tree[i] = tree[2*i+1];
      i /= 2;
    }
  }
  
  T get(int a, int b) {
    a += N;
    b += N;
    T r = inf;
    while (a < b) {
      if (a % 2 == 1) {
	if (cmp(tree[a], r))
	  r = tree[a];
	a++;
      }
      if (b % 2 == 0) {
	if (cmp(tree[b], r))
	  r = tree[b];
	b--;
      }
      a /= 2;
      b /= 2;
    }
    if (a == b) {
      if (cmp(tree[a], r))
	r = tree[a];
    }
    return r;
  }
};

const int max_size = 1<<17;
int main() {
  seqtree<int, max_size, less<int>, 1<<30> mintree;
  seqtree<int, max_size, greater<int>, -(1<<30)> maxtree;
  vector<int> vals(max_size);
  
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    vals[i] = a;
    mintree.set(i, a);
    maxtree.set(i, a);
  }
  
  for (int i = 0; i < q; i++) {
    char c;
    int a, b;
    cin >> c >> a >> b;
    if (c == '!') {
      swap(vals[a], vals[b]);
      mintree.set(a, vals[a]);
      mintree.set(b, vals[b]);
      maxtree.set(a, vals[a]);
      maxtree.set(b, vals[b]);
    } else {
      int m = mintree.get(a, b);
      int M = maxtree.get(a, b);
      if (M-m == b-a)
	cout<<"10-4\n";
      else
	cout<<"QAQ\n";
    }
  }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED