思维题……
最关键的一步是想到 刻画楼梯的右边界和下边界，剩下的就顺理成章了。
假设我们从右上到左下走楼梯的边界，用 \(1\) 代表竖边，\(0\) 代表横边，就能够得到一个长度为 \(p + 1\) 的序列。
例如题图：
我们从 \((1,4)\) 右侧开始走，到 \((5,1)\) 下侧结束，然后得到了长度为 \(9\) 的序列：
1 1 0 1 0 0 1 1 0。
考虑如何在这个序列上刻画子楼梯边界格数的信息：
设这个长度为 \(n = p + 1\) 序列为 \(A\)，对于每对满足 \(i < j, A_i = 1 \and A_j = 0\) 的 \((i, j)\)，\(j - i\) 都是一个合法的子楼梯边界格数。
先看询问。
若 \(n = 0\) 则一定无解。
显然 \(n = mq + 1(m \in \N^*)\)。
我们把 \(A_1, A_{q + 1}, A_{2q + 1}, \dots, A_{n}\) 拎出来为 \(B\) 序列。
问题转化为找到两个相邻项 \(B_{i}, B_{i + 1}\)，满足 \(B_i = 1 \and B_{i + 1} = 0\)。
由 \(A, B\) 的定义可以推知 \(B_1 = A_1 = 1, B_m = A_n = 0\)，所以若 \(n \ne 0\)，则一定有解。
接下来可以考虑二分。
若 \(B_{mid} = 0\)，则左半区一定存在解。
若 \(B_{mid} = 1\)，则右半区一定存在解。
再看修改。
操作 1 是在某个 \(1\) 后插入 \(b\) 个 \(0\)。
操作 2 是删去最后 \(b\) 个 \(0\)，若删到第 \(a\) 个 \(1\) 以前则立即停止，记删去 \(0\) 个数为 \(t\)，则在第 \(a\) 个 \(1\) 前放 \(t\) 个 \(0\)。
操作 3 就是回溯。
综上，可以用动态开点可持久化线段树来维护 \(A\)，时间复杂度是询问的 \(\mathcal O(n \log n \log V)\)，其中 \(\sup V = 10^9\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 3e5 + 10;
int m, rt[N];
namespace SGT {
#define lson t[pos].ls
#define rson t[pos].rs
int tot;
struct Seg {
ll w; int ls, rs;
} t[N * 160];
inline int newt(int pos) {t[++tot] = t[pos]; return tot;}
inline void pushup(int pos) {t[pos].w = t[lson].w + t[rson].w;}
void upd(int &pos, int l, int r, int x, ll c) {
t[pos = newt(pos)].w += c; if (l == r) return;
int mid = (l + r) >> 1;
x <= mid ? upd(lson, l, mid, x, c) : upd(rson, mid + 1, r, x, c);
}
void del(int &pos, int l, int r, int x) { // [x, +inf)
if (!pos || x > r) return;
if (x <= l) {pos = 0; return;}
pos = newt(pos); int mid = (l + r) >> 1;
del(lson, l, mid, x), del(rson, mid + 1, r, x);
pushup(pos);
}
ll qx(int pos, int l, int r, int x) { // [x, +inf)
if (!pos || x > r) return 0;
if (x <= l) return t[pos].w;
int mid = (l + r) >> 1;
return qx(lson, l, mid, x) + qx(rson, mid + 1, r, x);;
}
int qp(int pos, int l, int r, ll p) {
if (l == r) return p == 1 ? l : -l;
int mid = (l + r) >> 1;
if ((mid - l + 1) + t[lson].w >= p) return qp(lson, l, mid, p);
return qp(rson, mid + 1, r, p - (mid - l + 1) - t[lson].w);
}
int qlast(int pos, int l, int r, ll sz) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (t[rson].w >= sz) return qlast(rson, mid + 1, r, sz);
return qlast(lson, l, mid, sz - t[rson].w);
}
}
void getans(int o, ll l, ll r, ll len) {
if (l + 1 == r) {
int a = SGT::qp(o, 1, 1e9, 1 + l * len), b = -SGT::qp(o, 1, 1e9, 1 + r * len);
cout << a << ' ' << (SGT::qx(o, 1, 1e9, a) - (len - b + a) + 1) << '\n';
return;
}
ll mid = (l + r) >> 1;
SGT::qp(o, 1, 1e9, 1 + mid * len) > 0 ? getans(o, mid, r, len) : getans(o, l, mid, len);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> m;
for (int i = 1; i <= m; i++) {
char op; ll a, b; cin >> op >> a; rt[i] = rt[i - 1];
if (op == '+') {cin >> b, SGT::upd(rt[i], 1, 1e9, a, b);}
else if (op == '-') {
cin >> b;
if (a == 1 && SGT::t[rt[i]].w <= b) {rt[i] = 0; continue;}
int p = SGT::qlast(rt[i], 1, 1e9, b);
if (p >= a) {
SGT::upd(rt[i], 1, 1e9, p, SGT::qx(rt[i], 1, 1e9, p + 1) - b), SGT::del(rt[i], 1, 1e9, p + 1);
if (a > 1) SGT::upd(rt[i], 1, 1e9, a - 1, b);
} else {
if (a > 1) SGT::upd(rt[i], 1, 1e9, a - 1, SGT::qx(rt[i], 1, 1e9, a));
SGT::del(rt[i], 1, 1e9, a);
}
} else if (op == 'R') rt[i] = rt[i - a - 1];
else {
ll p = SGT::qlast(rt[i], 1, 1e9, 1) + SGT::t[rt[i]].w - 1;
if (!p) cout << "-1 -1\n";
else getans(rt[i], 0, p / a, a);
}
}
return 0;
}