P10222 [省选联考 2024] 最长待机 题解
Acoipp
·
·
题解
分析
这道题目主要是涉及到无限的概念，因此我们尝试抽丝剥茧并最终简化为一个形式化的问题。
最简单的部分
首先，有一个很显然的性质，如果询问的点 u 子树中的所有 e 都等于 0，那么等待的时间固定，我们为了满足公平，就只有构造出来一个等待时间相同的函数，并且不能有自己输入的变量。
具体而言，设等待 t 秒，那么我们设计的树就需要有 t 个叶子节点，答案显然是 t+[t \ge 2]。
当然，这道题并没有这部分分。
带有输入的数字
从最简单的出发，如果他的函数没有可供选择的 1，我的函数有，那我就可以用这个 1 来拉开与他的差距，他就不能够超过我，我必胜，这就是不可以出现的。
那如果他有一个 1，而我也恰好只有一个 1，但是他的那个 1 前面经过了 5 秒，我的 1 前面经过了 6 秒，那我就可以看到他输入的数字，进而确保自己胜利，我必胜，反过来同理，因此我们得到：
如果其中一者有 1，另一者也必须有 1 并且两者第一个 1 之前经过的时间必须相同。
这是必要条件，但是充分条件还需要经过一些推导才能得到，接下来继续。
如果他在经过一个 1 之后有再次决策的机会，而我在经过一个 1 之后就没有再次决策的机会了，那我必败，这也是不行的。
那么我们继续递推，就会发现：
> 如果树是一条链的话，那么他的 $1$ 的个数必须等于我的 $1$ 的个数。
### $e_1=1,\forall opt=2,k=1
考虑树不是一条链，B 性质怎么做，方便起见，我们可以看作所有 k 都等于 1。
这个时候从根节点就开始有 e=1 了，考虑把所有 e_i=0 的节点忽略，最终树可以拆分成若干条链。（因为非叶子节点的 e_i=0 没用，叶子节点的 e_i=0 能够被 e_j=1 的节点决定执行多少次，所以带来的影响只是常数，所以也没用）
那么显然，只有最长的那条链有用，设其链长为 len，答案就是 len。
证明
首先，设一个 e_i=0 输入的数为 1，e_i=1 输入的数为 x，那么我们就有 x+1=x，因为此时两个 x 同时输入，不知道大小关系，就算后面再等待 1 秒也没有区别，就等于让前面一个 x 减 1 了。
但是 1+x>x，因为此时 1 和 x 同时运行，左边的 x 可以看到右边的 x 输入的值，所以左边一定大于右边。
那么有 1x 就肯定有 2x，2x 可以表示为具有两个 e_i=1 的函数，但是这两个 e_i=1 并不是链上的关系，而是并列的关系，即形如 1 \to 2,1 \to3 这棵树 2 和 3 的关系。
还有就是 x+x=2x 和 x 个 2 相加是不一样的东西（尽管写出来都是 2x），并且如果一个常数乘上 x 比如 kx，如果 k 能够被其他 x 所决策/管辖，那么 kx=x，对于 x 的若干次项都满足这个条件；否则 kx>x。
进而就有 x^2,x^3,x^4 这种说法，考虑这种说法是什么意思 x^2 代表要执行 x 次输入 x 的运行程序，容易发现，x+x^2=x(1+x) > x^2，但是 x^2+x=x(x+1)=x^2，依次类推，高次项会吸收右边的低次项，这个定理对于 x^k(1 \le k) 都有用。
那么我们考虑一个节点他的 x 值是多少，首先他自己如果是 e_i=1，那么他就左边乘上一个 x，如果他有子树，那答案就是 x(\sum_{v \in son_u}A_v)，A_v 是一个关于 x 的多项式。
如果 e_i=0 那么他的 x 值就不需要乘上左边的那个 x。例如 x(1+2x+3+5x^2)=x^3，我们可以看作 x 个 1+2x+3+5x^2 相加的结果，那最高此项显然就是 5x^3，（根据前面的如果 k 能够有一个 x 决策管辖，那么 k 没用）所以这个等式成立。
当然如果 e_i=0，答案就是 1+2x+3+5x^2，因为根据前文所说高次项会吸收掉右边的低次项，所以答案变化为 1+2x+5x^2，但是这里为什么不等于 x^2 呢，因为这里他自己没有决策（根据前文 k 不被任意一个 x 管辖所以 k 有效），并且这三项必须同时决策才能确保游戏的公平，比如如果我的答案是 1+2x+5x^3 就不行，因为 x^3 严格大于 x^2。
那么证明到这里就很显然了，因为根节点为 1，所以答案就是他儿子的最高此项乘上 x，递归下去就是最长链的长度。
扩展
如果 e_i=0，这个在上面的证明中也提到过了，就是子节点的次数拿出来，用高次项消去低次项，但是需要保证次数非严格递增，然后设一共有 u 项，次数和是 s，在第一次决策前等待 t 秒，答案就是 t+s+[u+t \ge 2]。（不要合并同类项）
补充：根据证明容易得到 e_i=1 的话，A_i 一定只有一项，并且次数为 1。
综上 e_i=1 的问题很好解决，接下来我们解决 e_i=0 的问题。
## 处理
设 $p_i$ 表示 $i$ 到根节点的 $e=1$ 的数量，那么如果 $e_u=1$，那么答案就是 $\max_{v \in sonall_u}{p_v-p_u+1}$ 再加上一些前面等待的时。如果 $e_u=0$，我们可以发现，只考虑 $e_v=1$ 的节点 $v$ 在 dfs 序 $[l_u,r_u]$ 上的映射（$[l_u,r_u]$ 是 $u$ 子树在 dfs 序上的区间），那么一定是 $\min\dots \min \dots \min \dots$ 的形态（$\min$ 是在 $p_{l_u \sim r_u}$ 之间的最小值，但是要去掉所有 $e_i=0$ 的 $i$），此时 $\min=p_u+1$（显然可以证明），于是答案就是把所有 $\min$ 到下一个 $\min$ 或者 $r_u$ 中间的最大值拿出来，每个值都要减去 $p_u$（这是去掉 $u$ 到根节点上 $1$ 造成的影响，去掉影响之后答案就是 $A_i$ 的次数了），形成一个序列 $a$，对这个序列再进行高次项消去低次项的操作就可以了。
容易发现这个东西是可以合并的，然后每次使用线段树维护这个序列消去之后的一些信息就可以了，这一部分不是重点就不展开讲，可以参见 [P4198 楼房重建](https://www.luogu.com.cn/problem/P4198) 类似的处理方式。
## 代码
代码如下，常数偏大，时间复杂度为 $O(m \log^2 n)$（写得如果不够优雅有可能会 TLE）：
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define N 500005
namespace IO{
inline char nc(){
static char buf[1000000],*p=buf,*q=buf;
return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
ll res = 0,w = 1;
char c = nc();
while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
return res*w;
}
char obuf[1<<21],*p34=obuf;
inline void pc(char c){
p34-obuf<=(1<<20)?(*p34++=c):(fwrite(obuf,p34-obuf,1,stdout),p34=obuf,*p34++=c);
}
inline void write(ll x){
if(x>9) write(x/10);
pc(x%10+'0');
}
}
using namespace IO;
using namespace std;
vector<ll> op[N];
ll n,m,i,e[N],x,y,dfn[N],ot[N],dtot,nid[N],leaf[N],a[N],sta[N],top;
struct SGT{
struct node{
ll mx,mn,tag,len,ls,rs,lid,rid,mid,sum;
}tr[N<<2],temp;
inline void pushtag(ll p,ll c){
tr[p].mx += c,tr[p].mn += c,tr[p].tag += c,tr[p].ls += c,tr[p].rs += c,tr[p].mid += c,tr[p].sum += tr[p].len*c;
}
inline void pushdown(ll p){
pushtag(2*p,tr[p].tag),pushtag(2*p+1,tr[p].tag);
tr[p].tag = 0;
}
inline ll query_min(ll l,ll r,ll s,ll t,ll p){
if(l<=s&&t<=r) return tr[p].mn;
if(tr[p].tag) pushdown(p);
ll ans = 0x3f3f3f3f;
if(l<=(s+t)/2) ans=min(ans,query_min(l,r,s,(s+t)/2,2*p));
if(r>(s+t)/2) ans=min(ans,query_min(l,r,(s+t)/2+1,t,2*p+1));
return ans;
}
inline ll query_max(ll l,ll r,ll s,ll t,ll p){
if(l>r) return -1;
if(l<=s&&t<=r){
if(abs(tr[p].mx)>n) return -1;
return tr[p].mx;
}
if(tr[p].tag) pushdown(p);
ll ans = -1;
if(l<=(s+t)/2) ans=max(ans,query_max(l,r,s,(s+t)/2,2*p));
if(r>(s+t)/2) ans=max(ans,query_max(l,r,(s+t)/2+1,t,2*p+1));
return ans;
}
inline void query_anss(ll l,ll r,ll s,ll t,ll p){
if(l<=s&&t<=r){
if(temp.len==-1) temp=tr[p];
else temp=merge(temp,tr[p],s,t,p);
return ;
}
if(tr[p].tag) pushdown(p);
if(l<=(s+t)/2) query_anss(l,r,s,(s+t)/2,2*p);
if(r>(s+t)/2) query_anss(l,r,(s+t)/2+1,t,2*p+1);
}
inline pair<ll,ll> query_ans(ll l,ll r,ll s,ll t,ll p){
temp.len=-1;
query_anss(l,r,s,t,p);
return make_pair(temp.len,temp.sum);
}
inline pair<ll,ll> query(ll val,ll mn,ll s,ll t,ll p){
if(s==t) return make_pair(0,0);
if(tr[p].tag) pushdown(p);
if(tr[2*p].mn<tr[2*p+1].mn) return query(val,mn,s,(s+t)/2,2*p);
if(tr[2*p].mn>tr[2*p+1].mn) return query(val,mn,(s+t)/2+1,t,2*p+1);
if(tr[2*p].rs<val){
pair<ll,ll> ans = query(max(val,tr[p].mid),mn,(s+t)/2+1,t,2*p+1);
if(tr[p].mid>=val) ans.first++,ans.second+=tr[p].mid;
return ans;
}
else{
pair<ll,ll> ans = query(val,mn,s,(s+t)/2,2*p);
ans.first += tr[p].len-tr[2*p].len,ans.second += tr[p].sum-tr[2*p].sum;
return ans;
}
}
inline node merge(node a,node b,ll s,ll t,ll p){
node c;
if(a.mn<b.mn) c=a,c.tag=0,c.mid=-1;
else if(a.mn>b.mn) c=b,c.tag=0,c.mid=-1;
else{
c.mn = a.mn,c.lid = a.lid,c.rid = b.rid,c.ls = a.ls,c.mid = query_max(a.rid,b.lid-1,1,n,1);
if(c.mid==-1) c.mid = -1e13;
ll newrs = max(a.rs,c.mid);
pair<ll,ll> poly = query(newrs,c.mn,s,t,p);
c.rs = max(newrs,b.rs),c.len = a.len + (c.mid>=a.rs) + poly.first,c.sum = a.sum + (c.mid>=a.rs)*c.mid + poly.second;
}
if(abs(a.mx)>n&&abs(b.mx)>n) c.mx=max(a.mx,b.mx);
else if(abs(a.mx)>n) c.mx=b.mx;
else if(abs(b.mx)>n) c.mx=a.mx;
else c.mx=max(a.mx,b.mx);
return c;
}
inline void build(ll s,ll t,ll p){
if(s==t){
tr[p].mx = tr[p].mn = a[s],tr[p].tag = 0,tr[p].ls = tr[p].rs = a[s],tr[p].len = 0,tr[p].lid = tr[p].rid = s,tr[p].sum = 0,tr[p].mid = -1;
return ;
}
build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
if(tr[2*p].mn<tr[2*p+1].mn) tr[p]=tr[2*p];
else if(tr[2*p].mn>tr[2*p+1].mn) tr[p]=tr[2*p+1];
else{
tr[p].mn = tr[2*p].mn,top = 0;
ll sums = 0,midd = -1;
for(ll i=s,j;i<=t;){
if(i>=tr[2*p].rid&&i<tr[2*p+1].lid&&abs(a[i])<=n) midd=max(midd,a[i]);
if(a[i]==tr[p].mn){
ll temp = a[i];
for(j=i+1;j<=t;j++){
if(a[j]==tr[p].mn) break;
if(abs(a[j])<=n){
temp=max(temp,a[j]);
if(j>=tr[2*p].rid&&j<tr[2*p+1].lid) midd=max(midd,a[j]);
}
}
if(j<=t){
if(!top||sta[top]<=temp) sta[++top]=temp,sums+=temp;
}
i=j;
}
else i++;
}
tr[p].ls = sta[1],tr[p].rs = sta[top],tr[p].len = top,tr[p].sum = sums,tr[p].lid = tr[2*p].lid,tr[p].rid = tr[2*p+1].rid,tr[p].mid = midd;
}
if(abs(tr[2*p].mx)>n&&abs(tr[2*p+1].mx)>n) tr[p].mx=max(tr[2*p].mx,tr[2*p+1].mx);
else if(abs(tr[2*p].mx)>n) tr[p].mx=tr[2*p+1].mx;
else if(abs(tr[2*p+1].mx)>n) tr[p].mx=tr[2*p].mx;
else tr[p].mx=max(tr[2*p].mx,tr[2*p+1].mx);
}
inline void modify(ll l,ll r,ll c,ll s,ll t,ll p){
if(l<=s&&t<=r) return pushtag(p,c),void();
if(tr[p].tag) pushdown(p);
if(l<=(s+t)/2) modify(l,r,c,s,(s+t)/2,2*p);
if(r>(s+t)/2) modify(l,r,c,(s+t)/2+1,t,2*p+1);
tr[p] = merge(tr[2*p],tr[2*p+1],(s+t)/2+1,t,2*p+1);
// cout<<"? "<<p<<" "<<s<<" "<<t<<" "<<tr[p].mx<<endl;
// cout<<"! "<<p<<" "<<s<<" "<<t<<" "<<tr[p].lid<<" "<<tr[p].rid<<" "<<tr[p].sum<<" "<<tr[p].ls<<" "<<tr[p].rs<<endl;
}
}tr;
void dfs(ll x){
dfn[x] = ++dtot,nid[dtot] = x;
if(op[x].size()==0) leaf[dtot]=leaf[dtot-1]+1;
else leaf[dtot]=leaf[dtot-1];
for(ll i=0;i<op[x].size();i++) dfs(op[x][i]);
ot[x]=dtot;
if(e[x]) a[dfn[x]]++,a[ot[x]+1]--;
else a[dfn[x]]+=1e12,a[dfn[x]+1]-=1e12;
}
int main(){
// freopen("18.in","r",stdin);
// freopen("18.out","w",stdout);
n=read(),m=read();
for(i=1;i<=n;i++){
e[i]=read(),x=read();
while(x--) y=read(),op[i].push_back(y);
}
dfs(1);
for(i=1;i<=n;i++) a[i]+=a[i-1];
tr.build(1,n,1);
while(m--){
x=read(),y=read();
if(x==1){
// continue;
if(e[y]==0) tr.modify(dfn[y],ot[y],1,1,n,1),tr.modify(dfn[y],dfn[y],-1e12,1,n,1),e[y]=1;
else tr.modify(dfn[y],ot[y],-1,1,n,1),tr.modify(dfn[y],dfn[y],1e12,1,n,1),e[y]=0;
// cout<<tr.tr[1].mx<<endl;
}
else{
ll valy = tr.query_max(dfn[y],dfn[y],1,n,1),valall = tr.query_max(dfn[y],ot[y],1,n,1);
// cout<<"! "<<valall<<endl;
if(e[y]==1){
write(valall-valy+1),pc('\n');
continue;
}
if(valall==-1){
ll temp = leaf[ot[y]]-leaf[dfn[y]-1];
if(temp>1) temp++;
write(temp),pc('\n');
}
else{
valy = tr.query_min(dfn[y],ot[y],1,n,1)-1;
ll leav = 0,tot = 0,sum = 0;
ll l=dfn[y],r=ot[y];
while(l<r){
ll mid=(l+r)/2;
if(tr.query_max(dfn[y],mid,1,n,1)>valy) r=mid;
else l=mid+1;
}
leav=leaf[r-1]-leaf[dfn[y]-1];
pair<ll,ll> ans = tr.query_ans(dfn[y],ot[y],1,n,1);
l=dfn[y],r=ot[y];
while(l<r){
ll mid=(l+r+1)/2;
if(tr.query_min(mid,ot[y],1,n,1)<=valy+1) l=mid;
else r=mid-1;
}
// cout<<valy<<" "<<tr.query_min(4,5,1,n,1)<<endl;
tot=ans.first,sum=ans.second-tot*valy;
// cout<<leav<<" "<<ans.first<<" "<<ans.second<<" "<<l<<endl;
if(tr.query_max(l,ot[y],1,n,1)==valall) tot++,sum+=valall-valy;
// cout<<valall<<" "<<valy<<" "<<tot<<" "<<sum<<endl;
write(leav+sum+(leav+tot>=2)),pc('\n');
}
}
}
return fwrite(obuf,p34-obuf,1,stdout),0;
}
/*
Input:
3 6
0 2 2 3
0 0
0 0
2 1
1 3
2 1
1 3
1 2
2 1
Output:
3
3
1
*/
```