题解：AT_joisc2013_spy スパイ (Spy)

Fire_flys · 2025-11-23 22:20:06 · 题解

这道题我一直在想怎么用扫描线来做，后面实在是没招了，然后再仔细一看数据范围，发现只要 O(n^2+m) 就可以过了。

进入正题，我们先转换一下题目。对于每个间谍计划输入的 x，y，它们以及它们的所有下属都会进行工作，也就是说，在 JOI 社形成的树中，以 x 为根节点的子树都会被覆盖到；在 IOI 社形成的树中，以 y 为根节点的子树都会被覆盖到，而对于任意一个点 i，完成任务的条件就是同时被两棵树覆盖到，也就是说这个点要在 x的子树里，也要在 y 的子树里。

那么如何处理这个问题呢？我们可以使用 DFS 序来解决这个问题。

设在深搜时 u 的进栈时间为 dfn_u，以 u 为根的子树大小为 siz_u，对于 [dfn_u，dfn_u+siz_u]，若存在节点 k，使得 dfn_k 在这个区间范围之内，则 k 为 u 或 u 的子树中的节点。

设 JOI 社，IOI 社形成的树的 DFS 序分别为 dfn1，dfn2，子树大小分别为 siz1，siz2 那么对于查询 i 完成了多少个任务，就变成了求在输入给出的 M 个二元组中，有多少个二元组 x，y 满足：

这个式子长得很像二维偏序，但是我不会打。所以我们重新看一下数据范围，发现 n 不超过 2000，且 dfn+siz 的值不会超过 n。

于是我们可以再转换一下来求上面那个式子。我们把 (dfn1_i,dfn2_i) 这个二元组视作二维平面上的一个点，那么 dfn1_i 为横坐标，dfn2_i 为纵坐标，上面那个不等式在平面上就相当于一个矩形，这个矩形以 (dfn1_x,dfn2_y) 为左下角，以 (dfn1_x+siz1_x,dfn2_y+siz2_y) 为右上角。而我们的目标，也就是求有多少个这样的矩形包含了 (dfn1_i,dfn2_i) 这个点。

那么，我们就可以运用二维差分的思想，每次读入一个二元组 x 和 y 就把上述矩形部分全部加 1 ，查询的时候看有多少个矩形覆盖了 (dfn1_i,dfn2_i) 这个点即可求出 i 这个员工完成了多少个任务。

差分部分时间复杂度 O(n^2+m)，每个查询 O(1)，总复杂度 O(n^2+m) 可以通过本题。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=5e5+10;
int dfn1[N],dfn2[N],num=0,siz1[N],siz2[N];
vector<int> g[N],p[N];
inline void dfs(int u,int fa){
    dfn1[u]=++num;
    siz1[u]=1;
    for(int v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        siz1[u]+=siz1[v];
    }
    return;
}
inline void dfs2(int u,int fa){
    dfn2[u]=++num;
    siz2[u]=1;
    for(int v:p[u]){
        if(v==fa)continue;
        dfs2(v,u);
        siz2[u]+=siz2[v];
    }
    return;
}
int n,m,root1,root2,q;//第一棵树的根节点和第二棵树的根节点 
int s[N][N];
inline void update(int x,int y,int a,int b){//将以(x,y)为左下角,(a,b)为右上角的矩形全部加1 
    s[x][y]+=1;
    s[x][b+1]-=1;
    s[a+1][y]-=1;
    s[a+1][b+1]+=1; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y;i<=n;i++){
        cin>>x>>y;
        if(x!=0)g[x].push_back(i),g[i].push_back(x);
        else root1=i;
        if(y!=0)p[y].push_back(i),p[i].push_back(y);
        else root2=i;
    }
    dfs(root1,0);
    num=0;dfs2(root2,0);
    //for(int i=1;i<=n;i++)cout<<"dfn1["<<i<<"]="<<dfn1[i]<<" ";cout<<"\n"; for(int i=1;i<=n;i++)cout<<"dfn2["<<i<<"]="<<dfn2[i]<<" ";cout<<"\n";
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        update(dfn1[x],dfn2[y],dfn1[x]+siz1[x]-1,dfn2[y]+siz2[y]-1);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            //cout<<s[i][j]<<" ";
        }
        //cout<<"\n";
    }
    for(int i=1;i<=n;i++)cout<<s[dfn1[i]][dfn2[i]]<<"\n";   
    return 芙芙天下第一！;
}