我也想要 hanghang 的 tag/ll/ll

· · 题解

给一个当前题解区没有的做法。

首先考虑哪些节点会对询问的 x 产生贡献，分成几类。

第一类和第三类是容易计算的。

我们考虑如何计算第二类的贡献，考虑 y 对 x 产生了贡献。

我们可以把贡献看成在边上。

考虑对于原树进行 top cluster 树分块，那么 x 到根的路径可以表示成 O(\sqrt n) 条簇路径的贡献+ O(\sqrt n) 个散点的贡献。

对于修改操作使用颜色段均摊，则我们只有 O(n+q) 次区间染色。

散点的颜色可以用 O(\sqrt n)-O(1) 的分块维护。

我们将染色操作带上 \pm 1 的贡献系数，表示染色或者删除之前的染色。

对于整块，我们需要一次染色操作带来的贡献，我们对于每个块，对于簇路径用桶维护出现节点有哪些，以及在簇路径上经过向右儿子的边的节点有哪些，对于桶做前缀和，那么我们可以 O(1) 计算出来 [l,r] 在簇路径上有多少个节点，那么我们一次染色对于一个块的影响可以 O(1) 得到，所以我们就可以在 O((n+q)\sqrt n) 的复杂度内解决，但是常数不是很小。

由于我们树分块似乎有 6\frac n B 个块，所以 B 要开大一些。

代码的块长没有调过。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,B=1.5e3,T=6*N/B+5;
int n,q,cnt1[T][N],cnt2[T][N],ch[N][2],val[N],sz[N];
int f[N],F[N],pos[N],C,sum[N];
namespace Node{
    array<int,2> t1[N],t2[N];
    int L[N],R[N],bl[N];
    inline void change(int l,int r,int t,int v){
        int p=bl[l],q=bl[r];
        if(p==q){
            for(int i=l;i<=r;++i) t1[i]={t,v};
            return;
        }
        for(int i=l;i<=R[p];++i) t1[i]={t,v};
        for(int i=p+1;i<q;++i) t2[i]={t,v};
        for(int i=L[q];i<=r;++i) t1[i]={t,v};
    }
    inline void init(){
        for(int i=1;i<=n;++i) bl[i]=(i-1)/B+1,t1[i]={0,-1};
        for(int i=1;i<=bl[n];++i) t2[i]={0,-1},L[i]=R[i-1]+1,R[i]=min(i*B,n);
    }
    inline int qry(int x){return max(t1[x],t2[bl[x]])[1];}
}
#define pii pair<int,bool>
inline pii dfs(int x,int s,int fa=0){
    if(!x) return {0,0};
    val[x]=s,f[x]=fa,sz[x]=1;
    pii t;
    int cnt=1,FL=0;
    t=dfs(ch[x][0],s,x),cnt+=t.first,FL+=t.second,s+=sz[ch[x][0]],sz[x]+=sz[ch[x][0]];
    t=dfs(ch[x][1],s,x),cnt+=t.first,FL+=t.second,sz[x]+=sz[ch[x][1]];
    if(cnt>=B||FL>1) pos[x]=++C,cnt=0;
    return {cnt,pos[x]||FL};
}
inline void dfs2(int x,int lst){
    if(!x) return;
    if(pos[x]){
        F[x]=lst,lst=x;
        for(int i=x;i!=F[x];i=f[i]){
            if(!f[i]) continue;
            ++cnt1[pos[x]][f[i]];
            if(i==ch[f[i]][1]) ++cnt2[pos[x]][f[i]];
        }
        for(int i=1;i<=n;++i) cnt1[pos[x]][i]+=cnt1[pos[x]][i-1],cnt2[pos[x]][i]+=cnt2[pos[x]][i-1];
        for(int i=1;i<=n;++i) cnt1[pos[x]][i]+=cnt1[pos[F[x]]][i],cnt2[pos[x]][i]+=cnt2[pos[F[x]]][i];
    }
    dfs2(ch[x][0],lst),dfs2(ch[x][1],lst);
}
struct node{
    int l,r,c;
    inline node(int _l=0,int _r=0,int _x=0){l=_l,r=_r,c=_x;}
    inline bool operator <(const node a)const{return l<a.l;}
};
set<node>S;
#define Iter set<node>::iterator
inline Iter split(int x){
    Iter it=S.lower_bound(node(x));
    if(it!=S.end()&&it->l==x) return it;
    --it;
    int c=it->c,L=it->l,R=it->r;
    S.erase(it),S.insert(node(L,x-1,c));
    return S.insert(node(x,R,c)).first;
}
inline void change(int l,int r,int x){
    Iter ed=split(r+1),st=split(l);
    S.erase(st,ed),S.insert(node(l,r,x));
}
inline void mdf(int L,int R,int x,int v){
    if(x==-1) for(int i=2;i<=C;++i) sum[i]+=(cnt1[i][R]-cnt1[i][L-1])*v;
    if(x==0) for(int i=2;i<=C;++i) sum[i]+=(cnt2[i][R]-cnt2[i][L-1])*v;
}
inline void assign(int l,int r,int x,int t){
    auto ed=split(r+1),st=split(l);
    for(auto it=st;it!=ed;++it) mdf(it->l,it->r,it->c,-1);
    S.erase(st,ed),S.insert(node(l,r,x)),mdf(l,r,x,1),Node::change(l,r,t,x);
}
inline int calc(int x){
    int ans=1+val[x],c=Node::qry(x);
    if(c==0) ans+=sz[ch[x][0]];
    if(c==1) ans+=sz[ch[x][0]]+sz[ch[x][1]];
    while(!pos[x]){
        if(!f[x]) return ans;
        if((c=Node::qry(f[x]))==-1) ++ans;
        else if(c==0&&x==ch[f[x]][1]) ++ans;
        x=f[x];
    }
    return ans+sum[pos[x]];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q,pos[0]=C=1;
    for(int i=1;i<=n;++i) cin>>ch[i][0]>>ch[i][1];
    dfs(1,0),dfs2(1,0),S.insert(node(1,n+1,-1)),mdf(1,n,-1,1),Node::init();
    for(int opt,l,r,x,i=1;i<=q;++i){
        cin>>opt;
        if(opt==1) cin>>l>>r>>x,assign(l,r,x,i);
        else cin>>x,cout<<calc(x)<<"\n";
    }
}