大家好，由于我非常喜欢线段树，所以我用线段树切了这题。
提供一种复杂度为 \(\mathcal{O}(n\log^2n)\) 线段树二分的做法。
我们想一下，我们要用线段树来优化什么操作。
我们想找到某个位置的数量和大于等于 \(k\)，这个地方显然是可以二分的，但是要用到区间求和。
同时我们用完这些团子之后要清空，但是不一定都是整个都被用了，可能是用了一部分，所以会有单点修改和区间覆盖成 \(0\)。
到这里线段树做法就很明确了，对于操作建树，对于每个一操作，单点修改。
对于二操作，利用二分找到位置，然后分类讨论。
如果说这个位置到最后的团子的个数恰好等于 \(k\)，求出区间价值和即为答案，将这一部分清空。
如果说这个位置到最后的团子的个数大于等于 \(k\)，那只需要把这个位置分出一部分来，然后将剩下的清空即可。
/**
* author: TLE_Automation
* creater: 2022.10.14
**/
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gc getchar
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 998244353;
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define debug cout << "i ak ioi" << "\n"
inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline char readchar() {static char buf[100000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;}
inline int read() { int res = 0, f = 0; char ch = gc();for (; !isdigit(ch); ch = gc()) f |= (ch == '-'); for (; isdigit(ch); ch = gc()) res = (res << 1) + (res << 3) + (ch ^ '0'); return f ? -res : res;}
int sc = 0;
struct Node {
int l, r, sum, num;
} stc[N];
namespace Seg {
#define lson rt << 1
#define rson rt << 1 | 1
struct node {
int l, r, len, Cover, sum, num;
} tree[N << 1];
inline void pushup(int rt) {
tree[rt].sum = tree[lson].sum + tree[rson].sum;
tree[rt].num = tree[lson].num + tree[rson].num;
}
inline void build(int rt, int l, int r) {
tree[rt].l = l, tree[rt].r = r;
tree[rt].len = r - l + 1, tree[rt].Cover = -1;
if(l == r) return;
int Mid = (l + r) >> 1;
build(lson, l, Mid), build(rson, Mid + 1, r);
}
inline void pushdown(int rt) {
if(tree[rt].Cover == -1) return;
tree[lson].sum = 0, tree[rson].sum = 0;
tree[lson].num = 0, tree[rson].num = 0;
tree[lson].Cover = tree[rt].Cover, tree[rson].Cover = tree[rt].Cover;
tree[rt].Cover = -1;
}
inline void update(int rt, int pos, int W, int Num) {
if(tree[rt].l > pos || tree[rt].r < pos) return;
if(tree[rt].l == tree[rt].r) {
tree[rt].sum = W, tree[rt].num = Num; return;
} pushdown(rt);
update(lson, pos, W, Num), update(rson, pos, W, Num);
pushup(rt);
}
inline void change(int rt, int l, int r) {
if(tree[rt].l > r || tree[rt].r < l) return;
if(tree[rt].l >= l && tree[rt].r <= r) {
tree[rt].sum = 0, tree[rt].num = 0;
tree[rt].Cover = 0; return;
} pushdown(rt);
change(lson, l, r), change(rson, l, r);
pushup(rt);
}
inline int Query_sum(int rt, int l, int r) {
if(tree[rt].l > r || tree[rt].r < l) return 0;
if(tree[rt].l >= l && tree[rt].r <= r) return tree[rt].sum;
pushdown(rt); return Query_sum(lson, l, r) + Query_sum(rson, l, r);
}
inline int Query_num(int rt, int l, int r) {
if(tree[rt].l > r || tree[rt].r < l) return 0;
if(tree[rt].l >= l && tree[rt].r <= r) return tree[rt].num;
pushdown(rt); return Query_num(lson, l, r) + Query_num(rson, l, r);
}
}
using namespace Seg;
inline int getans(int l, int r) {
return ((l + r) * (r - l + 1)) / 2;
}
inline bool Check(int Mid, int k) {
return (Query_num(1, Mid, sc) >= k);
}
signed main()
{
int n = read();
build(1, 1, n);
for(int i = 1; i <= n; i++) {
int opt = read();
if(opt & 1) {
int l = read(), r = read();
stc[++sc] = (Node) {l, r, getans(l, r), r - l + 1};
update(1, sc, getans(l, r), r - l + 1);
}
else {
int k = read();
int l = 1, r = sc, ans(0);
while(l <= r) {
int Mid = (l + r) >> 1;
if(Check(Mid, k)) ans = Mid, l = Mid + 1;
else r = Mid - 1;
}
if(Query_num(1, ans, sc) == k) {
int res = Query_sum(1, ans, sc);
sc = ans - 1;
print(res), putchar('\n');
change(1, ans, sc);
}
else {
int res = 0;
if(ans + 1 <= sc) res = Query_sum(1, ans + 1, sc);
if(ans + 1 <= sc) k -= Query_num(1, ans + 1, sc);
int L = stc[ans].l, R = stc[ans].r;
res += getans(R - k + 1, R);
R -= k;
stc[ans] = (Node) {L, R, getans(L, R), R - L + 1};
update(1, ans, getans(L, R), R - L + 1);
sc = ans;
print(res), putchar('\n');
change(1, ans + 1, sc);
}
}
}
return (0 - 0);
}