题解：P7124 [Ynoi2008] stcm

· · 题解

更好的阅读体验

非常好技巧题。

我们要让我们维护的集合依次等于树上每个子树点集的补集，那么就要钦定一个顺序让操作次数尽可能少。

我们考虑按照 dfs 序进行操作。假设一个子树 u 的 dfs 序区间为 [l_u, r_u]，则当集合中的点是该子树的补集时，也就是将 [1, l_u) 和 (r_u, n] 加入到点集中。

对于两个子树的 dfs 序区间要么包含，要么不交。因此我们考虑分治，进入分治函数时我们传入当前区间的左右端点 l, r 和点集 S 满足 S 中每个子树的 dfs 序区间都完全包含于 [l, r]。然后我们取区间中点 mid，则对于不跨过 mid 的区间我们把它归到左半边或右半边递归计算即可；对于所有跨过 mid 的区间，由于它们有交，它们一定互相包含。因此我们从外往里处理即可。

容易发现这样子下来分治深度最多只有 O(\log n) 层，每一层处理的复杂度是 O(n)，因此时间复杂度为 O(n \log n)；每一层里每个点最多被加入 2n 次，因此操作 1 的次数为 2 n \log n，可以通过。

#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
using namespace std;
int n,tim,dfn[N],id[N];
vector<int> G[N];
vector<pair<int,int> > S;
void dfs(int u){id[dfn[u]=++tim]=u;for(int v:G[u])dfs(v);S.push_back({dfn[u],tim});}
void solve(vector<pair<int,int> > vec,int l,int r)
{
    if(!vec.size())return;
    vector<pair<int,int> > ls,rs;
    if(l==r)return printf("=%d",id[l]),(void)0;
    int mid=l+r>>1,lb=l-1,rb=r+1;
    for(auto [lef,rig]:vec)
    {
        if(rig<=mid)ls.push_back({lef,rig});
        else if(lef>mid)rs.push_back({lef,rig});
        else {
            for(;lb+1<lef;lb++)printf("+%d",id[lb+1]);
            for(;rb-1>rig;rb--)printf("+%d",id[rb-1]);
            printf("=%d",id[lef]);
        }
    }
    for(int i=1;i<=lb-l+r-rb+2;i++)putchar('-');
    for(int i=mid+1;i<=r;i++)printf("+%d",id[i]);
    solve(ls,l,mid);
    for(int i=mid+1;i<=r;i++)putchar('-');
    for(int i=l;i<=mid;i++)printf("+%d",id[i]);
    solve(rs,mid+1,r);
    for(int i=l;i<=mid;i++)putchar('-');
}
main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)G[i].clear();
        for(int i=2,fa;i<=n;i++)scanf("%d",&fa),G[fa].push_back(i);
        S.clear(),tim=0,dfs(1),reverse(S.begin(),S.end()),solve(S,1,n);
        putchar('!'),putchar(10);
    }
    return 0;
}