クエリ全体を通して、\(i\) 番目に列に並んだヘビをヘビ \(i\) とし、その長さを \(l_i\) とします。

まず、重要な性質としてこの問題の操作では、ヘビが列に追加される順番とヘビが列を抜ける順番は同じです。よって、どんな時も列にいる前から \(k\) 番目のヘビは、それまで列を抜けたヘビの数を\(m\) とすると、ヘビ \((k+m)\) です。

また、前から\(k\) 番目のヘビの頭の座標は列の前から \(1,2,\ldots,k-1\) 番目のヘビの長さの総和です。つまり、各クエリにおいてそれまでに抜けたヘビの数 \(m\) と、\(l_{m+1}+l_{m+2}+ \ldots + l_{m+k-1}\) が求められればよいです。

前者は、先頭からヘビが抜ける度に \(m\) に \(1\) を加えていくことで求められます。後者は、 \(S_i=\sum_{k=1}^{i}l_k \) を満たす配列 \(S\) を随時求めていけばよいです。具体的には 、\(S_i=S_{i-1}+l_i\) を満たすため、ヘビが列に並ぶたびに \(S\) の末尾と追加されるヘビの長さから\(S\) の末尾に追加する必要がある要素が求められます。

実装の際は、ヘビの長さの合計は32bit整数型ではオーバーフローするため64bit整数型を利用する必要があることに注意してください。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    long long now = 0;
    vector<long long> x;
    int id = 0;
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            long long l;
            cin >> l;
            x.push_back(now);
            now += l;
        } else if (t == 2) {
            id++;
        } else {
            int k;
            cin >> k;
            k--;
            cout << x[id + k] - x[id] << "\n";
        }
    }
}