自动搬运

查看原文

来自洛谷，原作者为

	int_R 我在衡水上高三没空想你

搬运于2025-08-24 23:07:49，当前版本为作者最后更新于2024-12-29 20:17:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我这写的也太详细了。

首先大概还是要维护一下树的结构的，不过显然不能全部维护，所以每次 $1$ 操作时直接把那 $k$ 个长度为 $l$ 的链用一个节点表示。

更具体的，我们应当对一个节点记录 $pos,l,k,dep$，表示这个节点代表的一众原树节点为 $k$ 个长度为 $l$ 的链，这些点的编号为 $[pos,pos+kl-1]$，每个链的深度在 $[dep,dep+l-1]$ 之间。

现在一个节点代表着若干条链，如果我们要对其中一个链的其中一个点做一些事情，那么这些链就并不完全一样了。我们只需要把这条将要操作的链从中 split 出来，它就只代表它自己了。

更具体的，设这个点表示了 $k$ 条链，将要进行操作的是第 $p$ 条链中的点，我们将这个点分成三个点分别代表第 $[1,p-1],[p,p],[p+1,k]$ 条链的信息。

还有一个问题是我们如何找到原树的第 $x$ 个点现在被哪个点表示，只需要全局维护一个 set 来找到所有点的 $pos$ 中小于等于 $x$ 中最大的即可。

那么 $1$ 操作就比较简单了，直接做。$2$ 操作的话我们可以暴力递归子树删掉。实际上要递归的是所有 $dep$ 大于等于 $x$ 点深度的儿子的子树，所以存儿子也要开一个 set。当然最后也要对本身修改一下。

然后我们好像还有一个查询操作，所有修改在深度上都是区间加的形式，动态开点线段树即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define ll long long
using namespace std;
typedef pair<ll,int> P;
const int MAXN=3e5+10;
const int MAXT=1.3e7;
const ll INF=1e18;
int m,tot=1,fa[MAXN];ll n=1;
struct node{ll pos,l,k,d;}t[MAXN];
set <P> s,v[MAXN];
namespace T
{
    struct node{ll num,add;int ls,rs;}t[MAXT];int tot=1;
    inline void upd(int p,ll z)
        {t[p].num+=z,t[p].add+=z;}
    inline void push_down(int p)
    {
        upd(t[p].ls,t[p].add),upd(t[p].rs,t[p].add);
        t[p].add=0;return ;
    }
    inline void push_up(int p)
        {t[p].num=max(t[t[p].ls].num,t[t[p].rs].num);}
    void add(ll l,ll r,int p,ll x,ll y,ll z)
    {
        if(x<=l&&y>=r){upd(p,z);return ;}
        if(!t[p].ls) t[p].ls=++tot,t[p].rs=++tot;
        ll mid=(l+r)>>1;push_down(p);
        if(x<=mid) add(l,mid,t[p].ls,x,y,z);
        if(y>mid) add(mid+1,r,t[p].rs,x,y,z);
        push_up(p);return ;
    }
    inline void A(ll l,ll r,ll x){add(1,INF,1,l,r,x);}
}

inline int find(ll x)//找到对应节点
{
    auto it=s.lower_bound({x,MAXN});
    return prev(it)->second;
}

inline void create(int p,ll pos,ll l,ll k,ll d)//创建一个新节点
{
    t[++tot]={pos,l,k,d},s.insert({pos,tot});
    v[fa[tot]=p].insert({-d,tot});return ;
}

inline void split(int p,ll num)//分裂出来一条链
{
    ll pos=t[p].pos,l=t[p].l,k=t[p].k,d=t[p].d;
    if(num>1)
    {
        s.erase({pos,p}),create(fa[p],pos,l,num-1,d);
        s.insert({t[p].pos=pos+(num-1)*l,p});
    }
    if(num<k) create(fa[p],pos+num*l,l,k-num,d);
    t[p].k=1;return ;
}

void dfs(int p)//递归子树删除
{
    if(t[p].l) T::A(t[p].d,t[p].d+t[p].l-1,-t[p].k);
    s.erase({t[p].pos,p});for(P y:v[p]) dfs(y.second);
}

inline void insert(ll x,ll l,ll k)// 1 操作
{
    int p=find(x);ll num=(x-t[p].pos)/t[p].l+1;
    split(p,num),num=(x-t[p].pos)%t[p].l;
    create(p,n+1,l,k,t[p].d+num+1);
    T::A(t[p].d+num+1,t[p].d+num+l,k),n+=l*k;return ;
}

inline void erase(ll x)// 2 操作
{
    int p=find(x);ll num=(x-t[p].pos)/t[p].l+1;
    split(p,num),num=(x-t[p].pos)%t[p].l;
    auto it=v[p].begin();
    for(P now:v[p])
    {
        if(-now.first<=t[p].d+num) break;
        dfs(now.second),++it;
    }
    v[p].erase(v[p].begin(),it);
    T::A(t[p].d+num,t[p].d+t[p].l-1,-1);
    t[p].l=num;return ;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    t[1]={1,1,1,1},s.insert({1,1}),T::A(1,1,1);
    cin>>m;for(int op;m;--m)
    {
        cin>>op;ll x,l,k;
        if(op==1) cin>>x>>l>>k,insert(x,l,k);
        if(op==2) cin>>x,erase(x);
        if(op==3) cout<<T::t[1].num<<'\n';
    }
    return 0;
}