由于间隔不变，对于下面 \(3\) 个操作，只需记录起始位置与间隔即可。
对于无数人到达酒店：所有位置的起始点 \(\times 2\)，间隔 \(\times2\)，新的团队起始点为 \(1\)，间隔为 \(2\)。
对于 \(k\) 个人到达酒店：所有点的起始点 \(+k\) ，间隔不变，新的团队起始点为 \(0\)，间隔为 \(1\)。
对于查询 \(g\) 团队的第 \(x\) 个人：找到起始点的坐标用间隔计算即可。
考虑如何实现查询位置 \(x\) 的所属团队。
从现在往前撤销加法或乘法操作。假设最后一个操作是乘法，那么如果位置 \(x\) 是奇数答案就是这个操作的团队编号。否则，撤销这个乘法操作，等价于将 \(x\) 除以 \(2\) 。现在最后是连续的一段加法操作，用前缀和 \(\mathcal O(1)\) 撤销这段操作即可。如果小于这个加法段，二分查找即可。发现每次撤销完连续加法操作，\(x\) 要么除以 \(2\) 要么退出循环，至多执行 \(30\) 次。
考场上本来过了这道题，但因为查询 \(g\) 团队的第 \(x\) 个人中的 \(g\) 可以为 \(0\)，所以线段树要从 \(0\) 开始加而光荣爆 \(0\)。吐槽大样例没有这样的情况而数据全是这样的情况。
#define int ll
const int N = 3e5 + 5, p = 1e9 + 7;
struct segment_tree
{
int add[N << 2], mul[N << 2], sum[N << 2];
void pushup(int id) {
sum[id] = sum[id << 1] + sum[id << 1 | 1];
}
void pushdown(int id, int l, int r, int mid) {
if (mul[id] ^ 1) {
mul[id << 1] *= mul[id], mul[id << 1 | 1] *= mul[id];
mul[id << 1] %= p, mul[id << 1 | 1] %= p;
add[id << 1] *= mul[id], add[id << 1 | 1] *= mul[id];
add[id << 1] %= p, add[id << 1 | 1] %= p;
sum[id << 1] *= mul[id], sum[id << 1 | 1] *= mul[id];
sum[id << 1] %= p, sum[id << 1 | 1] %= p;
mul[id] = 1;
}
if (add[id]) {
sum[id << 1] += (mid - l + 1) * add[id], sum[id << 1 | 1] += (r - mid) * add[id];
sum[id << 1] %= p, sum[id << 1 | 1] %= p;
add[id << 1] += add[id], add[id << 1 | 1] += add[id];
add[id << 1] %= p, add[id << 1 | 1] %= p;
add[id] = 0;
}
}
void tadd(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x) return ;
if (l >= x && r <= y) return sum[id] += (r - l + 1) * k, add[id] += k, sum[id] %= p, void();
int mid = l + r >> 1;
pushdown(id, l, r, mid);
tadd(l, mid, x, y, k, id << 1), tadd(mid + 1, r, x, y, k, id << 1 | 1);
pushup(id);
}
void tmul(int l, int r, int x, int y, int k, int id) {
if (l > y || r < x) return ;
if (l >= x && r <= y) return add[id] *= k, mul[id] *= k, sum[id] *= k, add[id] %= p, mul[id] %= p, sum[id] %= p, void();
int mid = l + r >> 1;
pushdown(id, l, r, mid);
tmul(l, mid, x, y, k, id << 1), tmul(mid + 1, r, x, y, k, id << 1 | 1);
pushup(id);
}
int query(int l, int r, int x, int y, int id) {
if (l > y || r < x) return 0;
if (l >= x && r <= y) return sum[id];
int mid = l + r >> 1;
pushdown(id, l, r, mid);
return (query(l, mid, x, y, id << 1) + query(mid + 1, r, x, y, id << 1 | 1)) % p;
}
} T1, T2;
int Q, pos[N], tot, cnt, n, s[N];
signed main()
{
// freopen("ex_hotel2.in", "r", stdin);
// freopen("my2.out", "w", stdout);
read(Q);
n = Q;
// T1 : 起始点
// T2 : 间隔
T2.tadd(0, n, 0, 0, 1, 1);
while (Q--)
{
int op, x, y;
read(op, x);
if (op == 1)
{
++tot;
s[tot] = s[tot - 1] + x;
if (x == 0)
{
pos[++cnt] = tot;
T1.tmul(0, n, 0, tot - 1, 2, 1);
T2.tmul(0, n, 0, tot - 1, 2, 1);
T1.tadd(0, n, tot, tot, 1, 1);
T2.tadd(0, n, tot, tot, 2, 1);
}
else
{
T1.tadd(0, n, 0, tot - 1, x, 1);
T2.tadd(0, n, tot, tot, 1, 1);
}
}
else if (op == 2)
{
read(y);
int st = T1.query(0, n, x, x, 1); // 起始点
int dis = T2.query(0, n, x, x, 1); // 间距
write((st + (y - 1) * dis % p) % p), ptc('\n');
}
else
{
int now = tot;
int k = x;
bool flg = 0;
for (int i = cnt; i >= 0; now = pos[i], --i)
{
int tmp = s[now] - s[pos[i]];
// cout << tmp << endl;
if (k >= tmp)
{
k -= tmp;
if (k % 2 == 1)
{
write(pos[i]), ptc('\n');
flg = 1;
break;
}
else
{
k /= 2;
}
}
else
{
int l = pos[i], r = now;
// cout << l << ' ' << r << endl;
while (l < r)
{
int mid = l + r >> 1;
if (k < s[now] - s[mid]) l = mid + 1;
else r = mid;
}
write(l), ptc('\n');
flg = 1;
break;
}
}
if (!flg) puts("0");
}
}
return 0;
}