写完了才发现有人已经搬运了 LOJ 的……

先把我的版本放在这里，管理人员可以考虑选择哪个。

#include "testlib.h"
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int N, A[5000], B[5000];

pair<int, int> mn[5000 << 2], mx[5000 << 2];

void pushUp(int x){
    mn[x] = min(mn[x<<1], mn[(x<<1)+1]);
    mx[x] = max(mx[x<<1], mx[(x<<1)+1]);
}
void bul(int x, int l, int r){
    if(l == r){
        mn[x] = mx[x] = make_pair(A[l], l);
        return;
    }
    int m = (l + r) >> 1;
    bul(x<<1, l, m);
    bul((x<<1)+1, m+1, r);
    pushUp(x);
}

void mdf(int x, int l, int r, int p, int k){
    if(l == r){
        A[l] = k;
        mn[x] = mx[x] = make_pair(k, p);
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m)
        mdf(x<<1, l, m, p, k);
    else
        mdf((x<<1)+1, m+1, r, p, k);
    pushUp(x);
}
pair<int, int> queMn(int x, int l, int r, int ll, int rr){
    if(ll <= l && r <= rr)
        return mn[x];
    pair<int, int> ret(1e9, 0);
    int m = (l + r) >> 1;
    if(ll <= m)
        ret = queMn(x<<1, l, m, ll, rr);
    if(rr > m)
        ret = min(ret, queMn((x<<1)+1, m+1, r, ll, rr));
    return ret;
}
pair<int, int> queMx(int x, int l, int r, int ll, int rr){
    if(ll <= l && r <= rr)
        return mx[x];
    pair<int, int> ret(0, 0);
    int m = (l + r) >> 1;
    if(ll <= m)
        ret = queMx(x<<1, l, m, ll, rr);
    if(rr > m)
        ret = max(ret, queMx((x<<1)+1, m+1, r, ll, rr));
    return ret;
}

int main(int argc, char ** argv){
    registerTestlibCmd(argc, argv);
    // input data
    N = inf.readInt();
    for(int i=1; i<=N; i++)
        A[i] = inf.readInt();
    for(int i=1; i<=N; i++)
        B[i] = inf.readInt();
    bul(1, 1, N);
    // output data
    int Q = ouf.readInt(0, 300000, "Q");
    int a = 0, b = 0;
    for(int i=1; i<=Q; i++){
        a = ouf.readInt(1, N, "a" + to_string(i));
        b = ouf.readInt(1, N, "b" + to_string(i));
        if(a > b)
            quitf(_wa, "Range error: l > r!");
        if(a != b){
            pair<int, int> mx = queMx(1, 1, N, a, b);
            pair<int, int> mn = queMn(1, 1, N, a, b);
            mdf(1, 1, N, mx.second, mn.first);
            mdf(1, 1, N, mn.second, mx.first);
        }
    }
    // answer check
    for(int i=1; i<=N; i++) if(A[i] != B[i])
        quitf(_wa, "Answer sequence not match!");

    quitf(_ok, "Answer correct!");
    return 0;
}