C++ 解法, 执行用时: 596ms, 内存消耗: 6432K, 提交时间: 2022-03-10 21:23:54

#include <bits/stdc++.h>
const int MaxN = 2e5 + 5;

int q, a[MaxN], c[MaxN];
int fa[MaxN], ch[MaxN][2], mx[MaxN];

void pushup(int x)
{
	mx[x] = x;
	for(int p : {ch[x][0], ch[x][1]})
	if(std::tie(a[mx[p]], mx[p]) > std::tie(a[mx[x]], mx[x])) mx[x] = mx[p];
}

bool isroot(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}

int get(int x) {return (ch[fa[x]][0] == x ? 0 : 1);}

void rotate(int x)
{
	int k = get(x), y = fa[x], z = fa[y];
	if(!isroot(y)) ch[z][get(y)] = x;
	ch[y][k] = ch[x][k ^ 1]; fa[ch[y][k]] = y;
	ch[x][k ^ 1] = y; fa[y] = x; fa[x] = z;
	pushup(y); pushup(x);
}

void splay(int x)
{
	for(int f = fa[x]; !isroot(x); rotate(x), f = fa[x])
	if(!isroot(f)) rotate(get(x) == get(f) ? f : x);
}

void access(int x)
{
	for(int p = 0; x; p = x, x = fa[x]) splay(x), ch[x][1] = p, pushup(x);
}

int main()
{
	int64_t lastans = 0;
	std::cin >> q >> c[1] >> a[1];
	pushup(1);
	
	for(int i = 1, opt, f, v, w; i <= q; ++i)
	{
		std::cin >> opt;
		if(opt == 1)
		{
			std::cin >> f >> c[i + 1] >> a[i + 1];
			fa[i + 1] = (f + lastans) % i + 1;
			pushup(i + 1);
		}
		else
		{
			std::cin >> v >> w; ++v;
			access(v);
			
			int cnt = 0; int64_t sum = 0;
			
			while(true)
			{
				splay(v);
				int t = mx[v]; if(a[t] == 0) break;
				int x = std::min(c[t], w);
				cnt += x; sum += int64_t(x) * a[t];
				if((c[t] -= x) == 0) splay(t), a[t] = 0, pushup(t);
				if((w -= x) == 0) break;
			}
			
			std::cout << cnt << " " << sum << "\n";
			lastans = cnt + sum;
		}
	}
	return 0;
}