P10222 [省选联考 2024] 最长待机 题解
PosVII
·
·
题解
前言
省选 100+12+0+100+0+0=212
小丑分数回归 whk 课了。所以没时间写代码，可能会在这两天把代码写完。
upd：写完了。为什么我 3.7 的题解比 3.10 的题解审的要晚啊，急眼了。。。
这题本质上还是个套着 adhoc 皮的 DS。
@[Linkwish](https://www.luogu.com.cn/user/408180) 与我共同 AC 此题！！！！
### 正文
------------
我们视一条长度为 $y$ 的全是 $1$ 的链为 $x^y$。
结论：
1. $x^y = x \times (nx^{y-1})$（$n$ 为常数），因为此时我们并不能保证最上面的那个 $1$ 中谁输入的 $x$ 更大，所以 $n$ 的影响只是常数级别，可以忽略不计。
1. $x^y+x^{y-1}=(x+1) \times x^{y-1}=x^y$，后面的 $x^{y-1}$ 对式子只有常数上的影响，所以可以忽略不计。
1. $x^{y-1}+x^y>x^y$，因为左式的 $x^{y-1}$ 和右式的 $x^y$ 同时输入，所以可以保证左式的 $x^y$ 比右式大，不能忽略。
考虑 adhoc 部分，我们根据上述结论，对询问的情况分类讨论：
1. $e_{k}=1$，所以此时的答案和 $k$ 所在的子树中，与 $k$ 的 $1$ 最多的链的 $1$ 的数量有关。
1. $e_{k}=0$，此时我们从 $k$ 向下遍历直到遍历到第一个 $1$ 或者叶子结点的 $0$，把它的答案（根据 $e_k = 1$ 部分的答案）从左到右排序，形成一个序列，它的答案就是不能被忽略的数的和，即那些左边没有数字比它大的数的和。
此时就可以 $O(nm)$ 暴力了，可以结合我下面给出的暴力理解。
```cpp
#include<bits/stdc++.h>
template<typename G>inline void read(G&x) {G f=1;x=0;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();x*=f;}
using namespace std;
const int MAXN=2e5+5;
int n,m;
bool c[MAXN];
vector<int> G[MAXN],vec;
int bfs(int u,int dep) {
int res=dep;
for(auto v:G[u]) res=max(res,bfs(v,dep+c[v]));
return res;
}
void dfs(int u) {
if(c[u]) {
vec.emplace_back(bfs(u,1));
return;
}
else if(G[u].empty()) vec.emplace_back(0);
for(auto v:G[u]) dfs(v);
}
int op,x;
signed main() {
read(n),read(m);
for(int i=1,k,v;i<=n;++i) {
read(c[i]),read(k);
for(int j=1;j<=k;++j) {
read(v);
G[i].emplace_back(v);
}
}
while(m--) {
read(op),read(x);
if(op==1) c[x]^=1;
else {
vec.clear(),dfs(x);
if(vec.size()==1) printf("%d\n",vec[0]+(vec[0]==0));
else {
int las=-1,ans=0,tot=0;
for(auto i:vec) {
if(i>=las) {
if(i==0) ++ans;
else ans+=i;
++tot,las=i;
}
}
printf("%d\n",ans+(tot!=1));
}
}
}
return 0;
}
```
发现直接记录每个 $1$ 点的答案是难以修改和查询的，考虑对其进行转化，设 $ans_i$ 是 $i$ 点到根的路径上 $1$ 的数量，发现 $e_k=1$ 的答案就是 $max^r_l\ e_i-e_{k}+1$。$ans_i$ 的维护是平凡的，线段树即可。
如果按上述的方法求 $e_k=0$ 的答案，这是复杂且非常不可做的。我们发现，如果把叶子节点强行设为 $1$，此时从 $k$ 往下走找到的每一个 $e_x = 1$ 的 $ans_x$ 都是相同的，所以我们可以把答案变成在 $[l,r]$ 的 dfs 序上找到若干个最小的 $ans_i$ 把它分割成若干个区间，而得到的序列就是这若干个区间各自的最大值。发现这个区间的分割是可以合并的，所以考虑使用兔队线段树维护。
时间复杂度 $O(m \log^2 n)$，常数一般，应该能过。
upd: 过了，代码如下：
```cpp
#include<bits/stdc++.h>
template<typename G>inline void read(G&x) {G f=1;x=0;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();x*=f;}
using namespace std;
#define int long long
const int MAXN=5e5+5;
int n,m;bool c[MAXN];
int L[MAXN],R[MAXN],dep[MAXN],idx[MAXN],cnt;
struct node {
int k,pre,suf,v,ans,mx,tot;
}d[MAXN<<2];
struct Fenwick_Tree {
int n,d[MAXN];
void init(int x) {n=x;}
void add(int x,int y) {for(int i=x;i<=n;i+=(i&-i)) d[i]+=y;}
int query(int x) {int res=0;for(int i=x;i;i-=(i&-i)) res+=d[i];return res;}
}BIT;
struct Segment_Tree {
bool leaf[MAXN<<2];
int lazy[MAXN<<2];
void pushdown(int p) {
if(lazy[p]) {
modify(p<<1,lazy[p]);
modify(p<<1|1,lazy[p]);
lazy[p]=0;
}
}
pair<int,int> Merge(node&x,int p) {
if(d[p].mx<x.mx) return make_pair(0,0);
if(leaf[p]) {
x.ans+=d[p].ans,++x.tot;
return make_pair(d[p].ans,d[p].ans);
}pushdown(p);
if(d[p<<1].mx>=x.mx) {
auto las=Merge(x,p<<1);
if(x.v<d[p<<1|1].v) {
if(las.first==las.second) x.ans-=las.first,--x.tot;
las.first=max(las.first,d[p<<1|1].mx),las.second=max(las.second,d[p<<1|1].mx);
if(las.first==las.second) x.ans+=las.first,++x.tot;
return las;
}
else {
if(x.v==d[p<<1].v) {
x.ans+=(d[p].ans-d[p<<1].ans),x.tot+=(d[p].tot-d[p<<1].tot);
las.first=d[p<<1|1].suf,las.second=max(las.second,d[p<<1|1].mx);
}
else {
if(las.first==las.second) x.ans-=las.first,--x.tot;
las.first=max(las.first,d[p<<1|1].pre),las.second=max(las.second,d[p<<1|1].pre);
if(las.first==las.second) x.ans+=las.first,++x.tot;
x.ans+=d[p].ans,x.tot+=d[p].tot;
las.first=d[p<<1|1].suf,las.second=max(las.second,d[p<<1|1].mx);
}
return las;
}
}
return Merge(x,p<<1|1);
}
node merge(node x,int p) {
if(x.v<d[p].v) {
if(x.suf==x.mx) x.ans-=x.suf,--x.tot;
x.suf=max(x.suf,d[p].mx),x.mx=max(x.mx,d[p].mx);
if(x.suf==x.mx) x.ans+=x.suf,++x.tot;
return x;
}
else if(x.v==d[p].v) {
if(x.mx>d[p].pre) {
Merge(x,p);
x.suf=d[p].suf,x.mx=max(x.mx,d[p].mx);
}
else {
if(x.suf==x.mx) x.ans-=x.suf,--x.tot;
x.ans=x.ans+d[p].pre+d[p].ans,x.tot=x.tot+1+d[p].tot;
x.suf=d[p].suf,x.mx=max(x.mx,d[p].mx);
}
return x;
}
else {
if(x.mx>d[p].pre) {
x.ans=0,x.tot=0,x.suf=d[p].suf,x.v=d[p].v,x.k=d[p].k;
Merge(x,p);
x.pre=max(x.mx,d[p].pre),x.mx=max(x.mx,d[p].mx);
return x;
}
else return d[p];
}
}
void modify(int p,int c) {
lazy[p]+=c;
d[p].ans+=c*d[p].tot,d[p].v+=c,d[p].mx+=c,d[p].pre+=c,d[p].suf+=c;
}
void modify(int l,int r,int ql,int qr,int p,int c) {
if(l>=ql&&r<=qr) {
modify(p,c);
return;
}
int mid=(l+r)>>1;pushdown(p);
if(ql<=mid) modify(l,mid,ql,qr,p<<1,c);
if(qr>mid) modify(mid+1,r,ql,qr,p<<1|1,c);
d[p]=merge(d[p<<1],p<<1|1);
}
void modify(int l,int r,int k,int p) {
if(l==r) {
d[p].v=1e9,d[p].mx=-1e9;
if(c[idx[l]]) d[p].v=d[p].mx=BIT.query(l);
d[p].k=l,d[p].ans=d[p].suf=d[p].mx,d[p].pre=-1e9,d[p].tot=1;
return;
}
int mid=(l+r)>>1;pushdown(p);
if(k<=mid) modify(l,mid,k,p<<1);
else modify(mid+1,r,k,p<<1|1);
d[p]=merge(d[p<<1],p<<1|1);
}
int query(int l,int r,int ql,int qr,int p) {
if(l>=ql&&r<=qr) return d[p].mx;
int mid=(l+r)>>1;pushdown(p);
if(qr<=mid) return query(l,mid,ql,qr,p<<1);
if(ql>mid) return query(mid+1,r,ql,qr,p<<1|1);
return max(query(l,mid,ql,qr,p<<1),query(mid+1,r,ql,qr,p<<1|1));
}
void query(int l,int r,int ql,int qr,int p,node&res) {
if(l>=ql&&r<=qr) {
if(l==ql) res=d[p];
else res=merge(res,p);
return;
}
int mid=(l+r)>>1;pushdown(p);
if(ql<=mid) query(l,mid,ql,qr,p<<1,res);
if(qr>mid) query(mid+1,r,ql,qr,p<<1|1,res);
}
void build(int l,int r,int p) {
if(l==r) {
leaf[p]=1;
d[p].v=1e9,d[p].mx=-1e9;
if(c[idx[l]]) d[p].v=d[p].mx=dep[idx[l]];
d[p].k=l,d[p].ans=d[p].suf=d[p].mx,d[p].pre=-1e9,d[p].tot=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,p<<1),build(mid+1,r,p<<1|1);
d[p]=merge(d[p<<1],p<<1|1);
}
}SGT;
vector<int> G[MAXN],leaf;
void dfs(int u) {
dep[u]+=c[u];
L[u]=++cnt,idx[cnt]=u;
for(auto v:G[u]) dep[v]=dep[u],dfs(v);
R[u]=cnt;
if(G[u].empty()) leaf.emplace_back(L[u]);
if(c[u]) BIT.add(L[u],1),BIT.add(R[u]+1,-1);
}
int fa[MAXN],op,x;
signed main() {
read(n),read(m);BIT.init(n);
for(int i=1,j,k;i<=n;++i) {
read(c[i]),read(k);
while(k--) {
read(j);fa[j]=i;
G[i].emplace_back(j);
}
}
dfs(1);
SGT.build(1,n,1);
while(m--) {
read(op),read(x);
if(op==1) {
c[x]^=1;
SGT.modify(1,n,L[x],1);
if(c[x]) {
SGT.modify(1,n,L[x],R[x],1,1);
BIT.add(L[x],1),BIT.add(R[x]+1,-1);
}
else {
SGT.modify(1,n,L[x],R[x],1,-1);
BIT.add(L[x],-1),BIT.add(R[x]+1,1);
}
}
else {
int val=BIT.query(L[fa[x]]);
node ans;SGT.query(1,n,L[x],R[x],1,ans);
int l=lower_bound(leaf.begin(),leaf.end(),L[x])-leaf.begin(),r=upper_bound(leaf.begin(),leaf.end(),R[x])-leaf.begin()-1;
int ll=l,rr=l-1;
while(l<=r) {
int mid=(l+r)>>1;
if(SGT.query(1,n,L[x],leaf[mid],1)<=val) l=mid+1,rr=mid;
else r=mid-1;
}
if(leaf[rr]==R[x]) printf("%lld\n",rr-ll+1+(rr-ll!=0));
else printf("%lld\n",ans.ans+(rr-ll+1)-ans.tot*val+(ans.tot+rr-ll!=0));
}
}
return 0;
}
```