galfth 解法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, blo, q, a[maxn], b[maxn], p1[maxn], p2[maxn], res, cnt1[maxn], cnt2[maxn], ans[maxn];
struct Query {
    int id, l, r;

    bool operator < (const Query &b) const {
        if (l / blo != b.l / blo)
            return l < b.l;
        return l / blo % 2 ? r < b.r : r > b.r;
    }

} query[4][maxn];

void add(int tp, int x) {
    if (tp == 1) {
        assert(cnt1[x] == 0);
        cnt1[x]++;
        if (cnt2[x]) res++;
    }
    else { // tp == 2
        assert(cnt2[x] == 0);
        cnt2[x]++;
        if (cnt1[x]) res++;
    }
}

void del(int tp, int x) {
    if (tp == 1) {
        assert(cnt1[x] == 1);
        cnt1[x]--;
        if (cnt2[x]) res--;
    }
    else { // tp == 2
        assert(cnt2[x] == 1);
        cnt2[x]--;
        if (cnt1[x]) res--;
    }
}

void cal(Query query[], bool add_or_del) {
    memset(cnt1, 0, sizeof(int)*(n+1));
    memset(cnt2, 0, sizeof(int)*(n+1));
    res = 0;
    sort(query, query+q);
    for (int i = 0, l = 0, r = 0; i < q; i++) {
        while (l < query[i].l) add(1, p1[++l]);
        while (l > query[i].l) del(1, p1[l--]);
        while (r < query[i].r) add(2, p2[++r]);
        while (r > query[i].r) del(2, p2[r--]);
        add_or_del ? (ans[query[i].id] += res) : (ans[query[i].id] -= res);
    }
}

int main() {
    scanf("%d", &n);
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
        p1[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", b+i);
        p2[b[i]] = i;
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        query[0][i] = {i, r1, r2};
        query[1][i] = {i, l1-1, r2};
        query[2][i] = {i, r1, l2-1};
        query[3][i] = {i, l1-1, l2-1};
    }
    for (int i = 0; i < 4; i++)
        cal(query[i], i==0 || i==3);
    for (int i = 0; i < q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

线段树：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

// 线段树 部分
int tr[maxn<<2];
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
void push_up(int rt) {
    tr[rt] = tr[rt<<1] + tr[rt<<1|1];
}
void add(int p, int x, int l, int r, int rt) {
    if (l == r) {
        tr[rt] += x;
        return;
    }
    int mid = (l + r) / 2;
    (p <= mid) ? add(p, x, lson) : add(p, x, rson);
    push_up(rt);
}
int _query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return tr[rt];
    int res = 0, mid = (l + r) / 2;
    if (L <= mid) res += _query(L, R, lson);
    if (R > mid) res += _query(L, R, rson);
    return res;
}

int n, q, a[maxn], b[maxn], pos[maxn], blo, ans[maxn];

struct Query {
    int id, l1, r1, l2, r2;

    bool operator < (const Query &b) const {
        if (l1 / blo != b.l1 / blo)
            return l1 < b.l1;
        return (l1 / blo % 2) ? (r1 < b.r1) : (r1 > b.r1);
    }
} query[maxn];

void add(int x) {
    int id = pos[x];
    add(b[id], 1, 1, n, 1);
}

void del(int x) {
    int id = pos[x];
    add(b[id], -1, 1, n, 1);
}

int main() {
    scanf("%d", &n);
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", b+i);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        query[i].id = i;
        scanf("%d%d%d%d", &query[i].l1, &query[i].r1, &query[i].l2, &query[i].r2);
    }
    sort(query, query+q);
    for (int i = 0, l = 1, r = 0; i < q; i++) {
        while (l < query[i].l1) del(l++);
        while (l > query[i].l1) add(--l);
        while (r < query[i].r1) add(++r);
        while (r > query[i].r1) del(r--);
        ans[query[i].id] = _query(query[i].l2, query[i].r2, 1, n, 1);
    }
    for (int i = 0; i < q; i++)
        printf("%d\n", ans[i]);
    return 0;
}