Kyselyt

#include <iostream>
using namespace std;
const int N = 1<<18;
int st1[2*N];
int st2[2*N];
int getMin(int a, int b) {
    a += N;
    b += N;
    int mi = 1e9;
    for(; a <= b; a/=2, b/=2) {
        if(a&1) mi = min(mi, st1[a++]);
        if(~b&1) mi = min(mi, st1[b--]);
    }
    return mi;
}
int getMax(int a, int b) {
    a += N;
    b += N;
    int ma = 0;
    for(; a <= b; a/=2, b/=2) {
        if(a&1) ma = max(ma, st2[a++]);
        if(~b&1) ma = max(ma, st2[b--]);
    }
    return ma;
}
void setValue(int a, int v) {
    a += N;
    st1[a] = st2[a] = v;
    for(a/=2; a; a/=2) {
        st1[a] = min(st1[a*2], st1[a*2+1]);
        st2[a] = max(st2[a*2], st2[a*2+1]);
    }
}
int main() {
    int n,q;
    cin>>n>>q;
    for(int i = 0; i< n; ++i) {
        cin>>st1[N+i];
        st2[N+i] = st1[N+i];
    }
    for(int a = N-1; a; --a) {
        st1[a] = min(st1[a*2], st1[a*2+1]);
        st2[a] = max(st2[a*2], st2[a*2+1]);
    }
    for(int i = 0; i < q; ++i) {
        char type;
        cin>>type;
        int a,b;
        cin>>a>>b;
        if(type == '!') {
            int a1 = st1[N+a-1];
            int b1 = st1[N+b-1];
            setValue(a-1, b1);
            setValue(b-1, a1);
        }
        else {
            if(b-a == getMax(a-1, b-1) - getMin(a-1, b-1)) {
                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