codeforces674D Bearish Fanpages

题目

Description

一个社交网站有nn个网页,第ii个公司拥有第ii个网页,每一个网页有一个父网页,不允许ii网页是jj网页的父网页且jj网页是ii网页的父网页,也不允许ii网页是自己的父网页,对于ii网页,设其父网页是j0j0网页,其子网页为j1,j2,...,jkj1,j2,...,jk,当用户浏览ii网页时,他们会看到来自k+2k+2家公司i,j0,j1,...,jki,j0,j1,...,jk的广告,有titi个用户喜欢第ii个网页,他们每个人都会点开一个广告看,对于k+1k+1家公司j0,j1,...,jkj0,j1,...,jk,会有tik+2\lfloor \frac{t_{i}}{k+2}\rfloor个用户点开他们家的广告,对于剩下的ti(k+1)tik+2t_{i}-(k+1)\lfloor \frac{t_{i}}{k+2}\rfloor个用户,他们会点开第ii家公司的广告。一个公司的总收入等于看他们家广告的用户数量。现在给出第ii个网页的父网页fifi,有qq个操作,操作分三种:

1ij1 i j:第ii个网页的父网页变成jj,保证之前第ii个网页的父网页不是jj

2i2 i:查询第ii家公司的总收入

33:输出这nn家公司的最少收入和最多收入

Input

第一行两整数nnqq分别表示公司数量和操作数量,之后输入nn个整数t1,...,tnt1,...,tn表示喜欢第ii个网页的用户数量,之后输入nn个整数f1,...,fnf1,...,fn表示第ii个网页的父网页,最后qq行每行一个操作$(3≤n≤105,1≤q≤105,1≤ti≤10^{12})

Output

对于查询操作,输出查询结果

Sample Input

5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3

Sample Output

10
36
28
40
36
9
57
27
28
29
9 57

题解

​ 不考虑3操作。

​ 考虑把x的父亲修改,会影响的结果只有原来x的父亲,后来x的父亲,x,以及与原来x的父亲相邻的点,与后来x的父亲相邻的点。

​ 考虑如果只是父亲或者父亲的父亲,我们可以直接修改,因为元素并不多。但是可能会存在儿子也要修改,这时候我们发现相当于是所有儿子的权值都减去某个值。

​ 显然这东西我们可以直接在他这个点打标记,每次查询的时候加上它的父亲就是真正的权值。

​ 考虑3操作。类似于ZJOI捉迷藏的点分治做法,我们对于每个点的儿子维护两个堆,再维护两个总的堆,每次修改的时候只需要把原来大堆中的元素删去,再加上这个堆的最值。

​ 出与懒惰,堆我直接用set来代替了,注意可能有重复元素,所以不能只存一个权值。

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
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll inf = 1ll << 60;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define pc putchar
#define gc getchar
#define fi first
#define se second
inline ll read(){
register ll x=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 1e5+233;
int A[maxn],D[maxn],n,Q;
ll B[maxn],E[maxn],C[maxn],F[maxn];
set<pair<ll,int> > s[maxn],mn,mx;
void del(int x){
ll w = F[A[x]];
bool flag1=false,flag2=false;
if(s[A[x]].begin() -> se == x){
mn . erase({s[A[x]].begin() -> fi + w,s[A[x]].begin() -> se});
flag1 = true;
}
if(s[A[x]].rbegin() -> se == x){
mx . erase({s[A[x]].rbegin() -> fi + w,s[A[x]].rbegin() -> se});
flag2 = true;
}
s[A[x]] . erase({C[x],x});
if(s[A[x]].size()){
if(flag1) mn . insert({s[A[x]].begin() -> fi+w,s[A[x]].begin()->se});
if(flag2) mx . insert({s[A[x]].rbegin() -> fi+w,s[A[x]].rbegin()->se});
}
}
void add(int x){
ll w = F[A[x]];
int flag1 = -1,flag2 = -1;
if(s[A[x]].size()){
flag1 = s[A[x]] . begin() -> se;
flag2 = s[A[x]] . rbegin() -> se;
}
s[A[x]] . insert({C[x],x});
if(flag1==-1){
mn . insert({s[A[x]].begin() -> fi+w,s[A[x]].begin()->se});
mx . insert({s[A[x]].rbegin() -> fi+w,s[A[x]].rbegin()->se});
} else{
if(flag1 != s[A[x]] . begin() -> se){
mn . erase({C[flag1] + w,flag1});
mn . insert({s[A[x]].begin()->fi + w,s[A[x]].begin()->se});
}
if(flag2 != s[A[x]] . rbegin() -> se){
mx . erase({C[flag2] + w,flag2});
mx . insert({s[A[x]].rbegin()->fi + w,s[A[x]].rbegin()->se});
}
}
}
void addF(int x,int det){
int w = F[x];
if(s[x].size()){
mn . erase({s[x].begin() -> fi + w,s[x].begin() -> se});
mx . erase({s[x].rbegin() -> fi + w,s[x].rbegin() -> se});
w += det;
mn . insert({s[x].begin()->fi + w,s[x].begin()->se});
mx . insert({s[x].rbegin()->fi + w,s[x].rbegin()->se});
}
}
void solve1(int x,int y){
ll det;
int w = A[x];
del(x),del(w),del(A[w]);
C[x] += F[w],C[x] -= (B[w] / D[w]),C[w] -= (B[x] / D[x]);
C[w] -= B[w] - D[w] * (B[w] / D[w]);
C[w] += B[w] - (D[w]-1) * (B[w] / (D[w] - 1));
det = (B[w] / (D[w]-1)) - (B[w] / D[w]);
D[w]--,C[A[w]] += det,C[w] += det;
addF(w,det),F[w] += det,add(w),add(A[w]);
A[x] = y,w = y,del(w),del(A[w]);
C[w] -= B[w] - D[w] * (B[w] / D[w]);
C[w] += B[w] - (D[w] + 1) * (B[w] / (D[w] + 1));
det = (B[w] / (D[w] + 1)) - (B[w] / D[w]);
D[w]++,C[A[w]] += det,C[w] += det,addF(w,det);
F[w] += det,C[w] += B[x] / D[x],C[x] += B[w] / D[w];
C[x] -= F[w],add(w),add(A[w]),add(x);
}
signed main(){
n = rd(),Q = rd();
Rep(i,1,n) B[i] = rd();
Rep(i,1,n){
A[i] = rd();
D[A[i]]++;D[i]++;
}
Rep(i,1,n) D[i] = 0;Rep(i,1,n) D[A[i]]++,D[i]++,D[i]++;
Rep(i,1,n) E[i] = B[i] / D[i]; Rep(i,1,n) C[i] = B[i] - D[i] * E[i];
Rep(i,1,n) C[A[i]] += E[i],C[i] += E[A[i]],C[i] += E[i];
Rep(i,1,n) s[A[i]] . insert({C[i],i});
Rep(i,1,n){
if(s[i].size()){
mn . insert(*s[i].begin());
mx . insert(*s[i].rbegin());
}
}
while(Q--){
int opt = rd();
if(opt == 1){
int x = rd(),y = rd();
solve1(x,y);
} else
if(opt == 2){
int x = rd();
writeln(C[x] + F[A[x]]);
} else
if(opt == 3){
write(mn.begin() -> fi);
pc(' ');
writeln(mx.rbegin() -> fi);
}
}
return 0;
}
文章目录
  1. 1. 题目
  2. 2. 题解