Liveddd's Blog

愛にできることはまだあるかい

P9168 [省选联考 2023] 人员调度

发表于 更新于 分类于
本文字数： 10k 阅读时长 ≈ 23 分钟

感觉还不错，感觉并没有特别困难。

考虑暴力，一个贪心策略是我们先找出子树的最优解，再尝试加上当前节点上的员工计算。贪心过程可以用堆实现。这里涉及到子树间信息的合并，使用启发式合并最终可以做到 $\mathcal O(n+qn\log^2n)$，获得 48 pts（当然使用可并堆可以少一支 $\log$，但是意义不大）。

Code 48pts
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
using ll=long long;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int type,n,k,m;
int a[N];
bool ban[N];
int tot,head[N],ver[N],ne[N];
int son[N],si[N];
vector<int>vec[N];
priority_queue<int,vector<int>,greater<int> >res[N];
ll ans;

inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void pre(int x)
{
    si[x]=1;
    for(int i=head[x];i;i=ne[i])
        pre(ver[i]),
        si[x]+=si[ver[i]],
        son[x]=si[ver[i]]>si[son[x]]?ver[i]:son[x];
}
void dfs(int x)
{
    if(son[x])
    {
        dfs(son[x]);
        swap(res[x],res[son[x]]);
    }
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==son[x])continue;
        dfs(y);
        while(!res[y].empty())
            res[x].push(res[y].top()),res[y].pop();
    }
    for(auto now:vec[x])
    {
        if(ban[now])continue;
        if(res[x].size()<si[x])ans+=a[now],res[x].push(a[now]);
        else if(res[x].top()<a[now])ans+=a[now]-res[x].top(),res[x].pop(),res[x].push(a[now]);
    }
}

inline void solve()
{
    ans=0;
    for(int i=1;i<=n;i++)while(!res[i].empty())res[i].pop();
    dfs(1);
    printf("%lld ",ans);
}
int main()
{
//    freopen("transfer.in","r",stdin);
//    freopen("transfer.out","w",stdout);
    read(type,n,k,m);
    for(int i=2,fa;i<=n;i++)read(fa),add(fa,i);
    for(int i=1,x;i<=k;i++)
    {chan
        read(x,a[i]);
        vec[x].push_back(i);
    }
    pre(1);
    solve();
    while(m--)
    {
        int op,x;
        read(op,x);
        if(op==1)
        {
            read(a[++k]);
            vec[x].push_back(k);
        }
        else ban[x]=1;
        solve();
    }
    cerr<<1000.0*clock()/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}

设二元组 $(x,v)$ 表示初始部门在点 $x$ 能力值为 $v$ 的员工。尝试找到一种简便的贪心策略。这一部分比较巧妙，对于点 $x$ ，设最优解中初始部门在子树 $x$ 的的点的个数为 $f(x)$，子树大小为 $s(x)$。考虑加入 $(x,v)$：

  1. 找到满足 $f(u)=s(u)$ 深度最大的 $x$ 的祖先 $u$。
  2. 删去权值最小的二元组，加入 $(x,v)$（如果更优的话）。

简单说明一下，对于 $u=x$ 显然正确。对于 $u\neq x$，那么在位置 $x$ 上的二元组必定来自祖先。加入尝试将位置 $x$ 空出，那么路径 $(u,x)$ 上的节点都向上移动，此时在 $u$ 上会多出一个二元组，它可以替换子树 $u$ 中任意一个二元组，替换权值最小的即可。

以上操作均可以使用树剖维护。但是删除操作并不好做，考虑使用线段树分治，将删除转为撤销。最终时间复杂度为 $\mathcal O(m\log m\log^2 n)$。

代码虽然比较长，但还是比较好写。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#define fir first
#define sec second
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int N=2e5+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int type,n,k,m;

namespace Dec
{
    int tot,head[N],ver[N<<1],ne[N<<1];
    int si[N],son[N],fa[N],dfn[N],num[N],top[N];
    struct Node
    {
        int l,r;
        PII s;//max{f(x)-s(x),dfn_pos}
        PII v;//min{val,pos}
        int tag;
    }tr[N<<2];
    void pushup(int x)
    {
        tr[x].s=max(tr[x<<1].s,tr[x<<1|1].s);
        tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);
    }
    void update(int x,int k){tr[x].s.fir+=k,tr[x].tag+=k;}
    void pushdown(int x)
    {
        if(!tr[x].tag)return ;
        update(x<<1,tr[x].tag),update(x<<1|1,tr[x].tag);
        tr[x].tag=0;
    }
    void build(int x=1,int l=1,int r=n)
    {
        tr[x].l=l,tr[x].r=r;
        if(l==r)return tr[x].s={-si[num[l]],l},tr[x].v={INF,num[l]},void();
        int mid=l+r>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void modify(int l,int r,int k,int x=1)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return update(x,k);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)modify(l,r,k,x<<1);
        if(r>mid)modify(l,r,k,x<<1|1);
        pushup(x);
    }
    void set(int pos,int k,int x=1)
    {
        if(tr[x].l==tr[x].r)return tr[x].v.fir=k,void();
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(pos<=mid)set(pos,k,x<<1);
        else set(pos,k,x<<1|1);
        pushup(x);
    }
    PII Pos(int l,int r,int x=1)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return tr[x].s;
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        PII res={-INF,0};
        if(l<=mid)res=max(res,Pos(l,r,x<<1));
        if(r>mid)res=max(res,Pos(l,r,x<<1|1));
        return res;
    }
    PII query(int l,int r,int x=1)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return tr[x].v;
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        PII res={INF,INF};
        if(l<=mid)res=min(res,query(l,r,x<<1));
        if(r>mid)res=min(res,query(l,r,x<<1|1));
        return res;
    }
    void add(int u,int v)
    {
        ver[++tot]=v;
        ne[tot]=head[u];
        head[u]=tot;
    }
    void dfs1(int x)
    {
        si[x]=1;
        for(int i=head[x];i;i=ne[i])
        {
            int y=ver[i];
            if(y==fa[x])continue;
            fa[y]=x;
            dfs1(y);
            si[x]+=si[y];
            if(si[son[x]]<si[y])son[x]=y;
        }
    }
    void dfs2(int x,int t)
    {
        num[dfn[x]=++*dfn]=x,top[x]=t;
        if(son[x])dfs2(son[x],t);
        for(int i=head[x];i;i=ne[i])
            if(ver[i]!=son[x]&&ver[i]!=fa[x])
                dfs2(ver[i],ver[i]);
    }
    int Jump(int x)
    {
        PII res={-INF,0};
        for(;x&&res.fir;x=fa[top[x]])res=max(res,Pos(dfn[top[x]],dfn[x]));
        if(res.fir)return 0;
        return num[res.sec];
    }
    void Set(int x,int k)
    {
        set(dfn[x],k);
    }
    void Modify(int x,int k)
    {
        for(;x;x=fa[top[x]])modify(dfn[top[x]],dfn[x],k);
    }
    PII Query(int x){return query(dfn[x],dfn[x]+si[x]-1);}
    void init()
    {
        for(int i=2,fa;i<=n;i++)read(fa),add(fa,i);
        dfs1(1);
        dfs2(1,1);
        build();
    }
}
namespace Solve
{
    PII a[N<<1];
    int L[N<<1],R[N<<1];
    vector<PII>tr[N<<2];
    multiset<int>s[N];//v
    int top;
    struct Node{int op;PII v;}sta[N<<2];
    ll ans;
    void modify(int ql,int qr,PII k,int x=1,int l=0,int r=m)
    {
        if(ql<=l&&r<=qr)return tr[x].push_back(k);
        int mid=l+r>>1;
        if(ql<=mid)modify(ql,qr,k,x<<1,l,mid);
        if(qr>mid)modify(ql,qr,k,x<<1|1,mid+1,r);
    }
    int cnt=0;
    inline void ins(PII x)
    {
        ans+=x.fir;
        cnt++;
        s[x.sec].insert(x.fir);
        Dec::Modify(x.sec,1);
        Dec::Set(x.sec,*s[x.sec].begin());
    }
    inline void del(PII x)
    {
        ans-=x.fir;
        cnt--;
        s[x.sec].erase(s[x.sec].find(x.fir));
        Dec::Modify(x.sec,-1);
        Dec::Set(x.sec,*s[x.sec].begin());
    }
    void dfs(int x=1,int l=0,int r=m)
    {
        int last=top;
        for(auto now:tr[x])
        {
            int u=Dec::Jump(now.sec);
            if(!u)ins(now),sta[++top]={1,now};
            else
            {
                PII val=Dec::Query(u);
                if(now.fir>val.fir)
                {
                    del(val),ins(now);
                    sta[++top]={0,val};
                    sta[++top]={1,now};
                }
            }
        }
        if(l==r)printf("%lld ",ans);
        else
        {
            int mid=l+r>>1;
            dfs(x<<1,l,mid),dfs(x<<1|1,mid+1,r);
        }
        for(;top>last;top--)
        {
            if(sta[top].op)del(sta[top].v);
            else ins(sta[top].v);
        }
    }
    void solve()
    {
        for(int i=1,x,v;i<=k;i++)read(x,v),a[i]={v,x},L[i]=0,R[i]=m;
        for(int i=1,op,x,v;i<=m;i++)
        {
            read(op,x);
            if(op==1)
            {
                read(v);
                a[++k]={v,x};
                L[k]=i,R[k]=m;
            }
            else R[x]=i-1;
        }
        for(int i=1;i<=k;i++)modify(L[i],R[i],a[i]);
        for(int i=1;i<=n;i++)s[i].insert(INF);
        dfs();
    }
}
int main()
{
    // freopen("transfer.in","r",stdin);
    // freopen("transfer.out","w",stdout);
    read(type,n,k,m);
    Dec::init();
    Solve::solve();
    return 0;
}