题意

多次询问有根树上 \(l\sim r\) 的 \(x\) 级祖先的并集大小。

点数 \(10^5\)，询问数 \(10^6\)，\(4\) 秒，\(1024\) MB。

题解

考虑 \(x\) 固定怎么做。

记一个点的颜色为一个点的 \(x\) 级祖先。首先深度不同的点颜色一定不同，可以分开考虑。

不难发现这是一个数颜色问题，维护一下 \(pre_i\) 表示上一个 \(x\) 级祖先相同的点，然后有贡献的要求就是 \(pre_i。这显然是好做的。

考虑 \(x\) 从小到大增加的时候，\(pre\) 如何变化，不难发现颜色不同的点可能会变得颜色相同，颜色相同的点颜色仍然相同。

我们对一个深度计算时，考虑建出深度为当前值的所有点的虚树，然后从下到上启发式合并，集合中存储这个子树里的点，考虑把小集合合并到大集合时，我们每插入一个点，至多改变两个点的 \(pre\)，于是我们的修改次数是 \(O(n\log n)\) 的。

但是我们不需要显示的建出虚树，可以通过倒着枚举每一层点的方式完成启发式合并的过程。

对于一个询问，我们初始认为所有点的颜色都不同，即答案是 \(r-l+1\)。但这显然比较倒闭，考虑什么样的点会导致答案 \(-1\)。

可以发现，若 \(pre_i\ge l,l\le i\le r\)，则答案要减去 \(1\)。又因为 \(i\ge pre_i\)，所以不需要限制 \(l\le i\)。

对于一次修改和一个询问，如果修改后 \(pre_i,i\) 满足上述限制，且修改时间在这次询问之前，则这次修改对这个询问有贡献。不难发现这实际上是三维偏序，可以使用 cdq 分治完成对询问贡献这一事情。

最后复杂度应该是 \(O((n\log n+m)\log n\log (n+m))\) 的。

代码

点击查看代码

#include
#define int long long
// #define ui unsigned int
// #define ll __int128
#define ull unsigned long long
#define N 100005
#define M 1000005
#define K 20
// #define B 13331
#define mod 1000000007
#define pii pair
#define x first
#define y second
#define pct __builtin_popcount
#define mpi make_pair
#define pi acos(-1)
#define inf 2e18
#define poly vector
using namespace std;
int Tc=1,n,m,rt,cnt,nw[N],dep[N],pre[N],res[M];
vectore[N];
void add(int a,int b){
    e[a].push_back(b);
}
dequef[N];
sets[N];
struct info{
    int l,t,p,op;
};
vectorall;
void ins(int l,int t,int p,int op){
    if(l<=n)all.push_back({l,t,p,op});
}
void modify(int t,int p,int l){
    ins(pre[p]+1,t,p,1);
    ins(l+1,t,p,-1);
    pre[p]=l;
}
struct qry{
    int t,p,op;
};
vectorq,a[N];
struct bit{
    int c[N];
    void add(int x,int v){
        while(x<=n){
            c[x]+=v;
            x+=x&-x;
        }
    }
    int qry(int x){
        int res=0;
        while(x){
            res+=c[x];
            x^=x&-x;
        }
        return res;
    }
}c;
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int mi=0;
    for(int i=l,j=mid+1;j<=r;j++){
        while(i<=mid&&q[i].t<=q[j].t){
            if(abs(q[i].op)==1)c.add(q[i].p,q[i].op);
            i++;
            mi=i;
        }
        if(q[j].op>1)res[q[j].op-1]-=c.qry(q[j].p);
    }
    for(int i=l;itmp;
    while(i<=mid&&j<=r){
        if(q[i].t<=q[j].t)tmp.push_back(q[i++]);
        else tmp.push_back(q[j++]);
    }
    while(i<=mid)tmp.push_back(q[i++]);
    while(j<=r)tmp.push_back(q[j++]);
    for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
void solve(int cs){
    if(!cs)return;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x)add(x,i);
        else rt=i;
    }
    nw[++cnt]=rt;
    for(int i=1;i<=n;i++){
        int u=nw[i];
        for(auto v:e[u]){
            dep[v]=dep[u]+1;
            nw[++cnt]=v;
        }
    }
    for(int o=n;o;o--){
        int u=nw[o],son=0;
        for(auto v:e[u]){
            if(!son||f[v].size()>f[son].size()){
                son=v;
            }
        }
        if(son)f[u]=move(f[son]);
        f[u].push_front(u);
        s[u].insert(u);
        for(auto v:e[u]){
            if(v==son)continue;
            for(int d=0;demp;
            f[v].swap(emp);
        }
    }
    for(int i=1;i<=n;i++){
        modify(dep[i]+1,i,i);
    }
    for(auto it:all){
        a[it.l].push_back({it.t,it.p,it.op});
    }
    for(int i=1;i<=m;i++){
        int l,r,x;
        cin>>l>>r>>x;
        a[l].push_back({x,r,i+1});
        res[i]=r-l+1;
    }
    for(int i=1;i<=n;i++){
        for(auto it:a[i]){
            q.push_back(it);
        }
    }
    if(!q.empty())cdq(0,q.size()-1);
    for(int i=1;i<=m;i++){
        cout<>Tc;
    // init();
    for(int cs=1;cs<=Tc;cs++){
        solve(cs);
    }
    // cerr<

QOJ9676 Ancestors 题解

题意

题解

代码