算法

(离线莫队，线段树) $O(m \sqrt n \log s)$

1. 直接暴力离线莫队，注意要配合上奇偶优化。注意线段树的最大区间为 [1, s]，这里的 s 是插入时的最大右端点。（可以离散化到 n）。
2. 最终，还是要靠 吸氧 O2。

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 50010;

int n, m, s;
int al[N], ar[N];
int unit;

struct Query {
    int l, r, id;
    bool operator < (const Query &x) const {
        if (l / unit != x.l / unit)
            return l < x.l;

        if ((l / unit) & 1)
            return r < x.r;

        return r > x.r;
  }
}q[N];

struct Node {
    int mm, who, tag;
}node[N << 2];

struct Ans {
    int mm, who;
}ans[N];


inline void pushdown(int rt) {
    if (node[rt].tag) {
        node[rt << 1].tag += node[rt].tag;
        node[rt << 1 | 1].tag += node[rt].tag;
        node[rt << 1].mm += node[rt].tag;
        node[rt << 1 | 1].mm += node[rt].tag;
        node[rt].tag = 0;
    }
}


inline void pushup(int rt) {
    if (node[rt << 1].mm >= node[rt << 1 | 1].mm) {
        node[rt].mm = node[rt << 1].mm;
        node[rt].who = node[rt << 1].who;
    } else {
        node[rt].mm = node[rt << 1 | 1].mm;
        node[rt].who = node[rt << 1 | 1].who;
    }
}


void build(int l, int r, int rt) {
    if (l == r) {
        node[rt].who = l;
        return;
    }

    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}


void modify(int L, int R, int x, int l, int r, int rt) {
    if (L <= l && r <= R) {
        node[rt].tag += x;
        node[rt].mm += x;
        return;
    }

    pushdown(rt);

    int mid = (l + r) >> 1;
    if (L <= mid) modify(L, R, x, l, mid, rt << 1);
    if (mid < R) modify(L, R, x, mid + 1, r, rt << 1 | 1);

    pushup(rt);
}


inline void modify(int pos, int sign) {
    modify(al[pos], ar[pos], sign, 1, s, 1);
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &al[i], &ar[i]);
        s = max(s, ar[i]);
    }

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }

    build(1, s, 1);

    unit = sqrt(n);

    sort(q + 1, q + 1 + m);

    int l = 1, r = 0;

    for (int i = 1; i <= m; i++) {
        const Query &x = q[i];
        while (l > x.l) modify(--l, 1);
        while (r < x.r) modify(++r, 1);
        while (l < x.l) modify(l++, -1);
        while (r > x.r) modify(r--, -1);

        ans[x.id].mm = node[1].mm;
        ans[x.id].who = node[1].who;

    }

    for (int i = 1; i <= m; i++)
        printf("%d %d\n", ans[i].who, ans[i].mm);

    return 0;
}