Kyselyt

#include<iostream>
#include<vector>

using namespace std;

struct node {
  int64_t min,max;
};

int64_t M=1;

void set(vector<node> &spuu, int64_t a, int64_t m) {
  a+=M;
  spuu[a].min=m;
  spuu[a].max=m;
  a/=2;
  while(a>=1) {
    spuu[a].min=min(spuu[2*a].min,spuu[2*a+1].min);
    spuu[a].max=max(spuu[2*a].max,spuu[2*a+1].max);
    a/=2;
  }
}

void get(vector<node> &spuu, int64_t a, int64_t b, int64_t &m, int64_t &Max) {
  a+=M;
  b+=M;
  while(a<=b) {
    m=min(spuu[a].min, m);
    m=min(spuu[b].min, m);
    Max=max(spuu[a].max, Max);
    Max=max(spuu[b].max, Max);
    a=(a+1)/2;
    b=(b-1)/2;
  }
}

int main(void) {
  int64_t n, q;
  cin >> n >> q;

  while(M<=2*n) M*=2;
  M/=2;
  vector<node> spuu(2*M);

  for(int64_t i=0;i<2*M;i++) {
    spuu[i].max=-1;
    spuu[i].min=(int64_t)100000000000;
  }

  for(int64_t i=0;i<n;i++) {
    int64_t a;
    cin >> a;
    set(spuu,i,a);
  }

  for(int64_t i=0;i<q;i++) {
    char c;
    int64_t a,b;
    cin >> c >> a >> b;
    a--;b--;
    if(c == '?') {
      int64_t min=1000000000000,max=-1;
      get(spuu, a, b, min, max);
      /*cout << "Max: " << max << " Min: " << min << endl;*/
      if(max-min==b-a) {
        cout << "10-4\n";
      } else {
        cout << "QAQ\n";
      }
    } else {
      int64_t tmp=spuu[M+a].max, rmp=spuu[M+b].max;
      set(spuu, a, rmp);
      set(spuu, b, tmp);
      /*for(int64_t i=0;i<spuu.size();i++) {
        cout << i << ": " << spuu[i].min << " " << spuu[i].max << endl;
      }*/
    }
  }
}

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