牛客练习赛97 F

LCT 板子，不多说了。

复杂度是可以均摊的。

typedef std::pair<ullt,uint>Pair;
struct LCT
{
    struct node
    {
        Pair val,max;node*son[2],*fath;bol tag;
        node(Pair v=Pair()):val(v),max(v),fath(NULL),tag(false){son[0]=son[1]=NULL;}
        voi pushup()
        {
            pushdown();
            max=val;
            if(son[0]!=NULL)_max(max,son[0]->max);
            if(son[1]!=NULL)_max(max,son[1]->max);
        }
        voi pushdown()
        {
            if(tag)
            {
                std::swap(son[0],son[1]);
                if(son[0]!=NULL)son[0]->tag^=1;
                if(son[1]!=NULL)son[1]->tag^=1;
                tag=false;
            }
        }
        bol howson(){return this==fath->son[1];}
        bol ifroot(){return fath==NULL||!(this==fath->son[0]||this==fath->son[1]);}
        voi rotate()
        {
            if(ifroot())return;
            node*f=fath;bol sk=howson();fath=f->fath;
            if(!f->ifroot())f->fath->son[f->howson()]=this;
            if((f->son[sk]=son[!sk])!=NULL)son[!sk]->fath=f;
            (son[!sk]=f)->fath=this;f->pushup(),pushup();
        }
        voi update()
        {
            if(!ifroot())fath->update();
            pushdown();
        }
        voi splay()
        {
            update();
            while(!ifroot())
            {
                if(!fath->ifroot())(howson()==fath->howson()?fath:this)->rotate();
                rotate();
            }
        }
    };
    std::vector<node*>N;
    voi insert(Pair p){N.push_back(new node(p));}
    node*get(uint n){return N[n];}
    voi bzr(){while(!N.empty()){delete N.back();N.pop_back();}}
    voi build(uint n){bzr();N.resize(n);for(uint i=0;i<n;i++)N[i]=new node;}
    voi build(Pair*A,uint n){bzr();N.resize(n);for(uint i=0;i<n;i++)N[i]=new node(A[i]);}
	node*access(node*p)
	{
		node*s=NULL;
		while(p!=NULL)p->splay(),p->son[1]=s,(s=p)->pushup(),p=p->fath;
		return s;
	}
    voi makeroot(node*p){access(p),p->splay(),p->tag^=1,p->pushdown();}
    voi split(node*p,node*q){makeroot(p),access(q),q->splay();}
    node*findroot(node*p)
    {
        access(p),p->splay(),p->pushdown();
        while(p->son[0]!=NULL)(p=p->son[0])->pushdown();
        p->splay();
        return p;
    }
    bol connected(node*p,node*q){return makeroot(p),p==findroot(q);}
    bol link(node*p,node*q)
    {
        if(connected(p,q))return false;
        makeroot(p),p->fath=q;return true;
    }
    bol cut(node*p,node*q)
    {
        split(p,q);
        if(p->fath!=q||q->son[0]!=p)return false;
        p->fath=q->son[0]=NULL;
        return true;
    }
    Pair ask(node*p,node*q){return split(p,q),q->max;}
    voi chg(node*p,Pair v){p->val=v,p->splay();}
}T;
ullt A[200005];
int main()
{
    uint q;scanf("%u",&q),scanf("%llu",A);
    ullt v,ans=0;scanf("%llu",&v),T.insert(Pair(v,0));
    for(uint i=1;i<=q;i++)
    {
        uint op;
        scanf("%u",&op);
        if(op==1)
        {
            uint f;scanf("%u%llu%llu",&f,A+i,&v);
            f=(f+ans)%i;
            T.insert(Pair(v,i));
            T.link(T.get(i),T.get(f));
        }
        else{
            uint p;scanf("%u%llu",&p,&v);
            ans=0;
            ullt qaq=0;
            while(true)
            {
                auto w=T.ask(T.get(0),T.get(p));
                if(!w.first)break;
                if(A[w.second]>=v)
                {
                    ans+=v*w.first,A[w.second]-=v;
                    qaq+=v;
                    break;
                }
                ans+=A[w.second]*w.first;
                v-=A[w.second];
                qaq+=A[w.second];
                A[w.second]=0;
                T.chg(T.get(w.second),Pair(0,w.second));
            }
            printf("%llu %llu\n",qaq,ans);
            ans+=qaq;
            T.insert(Pair(0,i));
        }
    }
	return 0;
}