灵异事件
  • 板块学术版
  • 楼主262620zzj
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/3 20:26
  • 上次更新2025/2/3 20:27:09
查看原帖
灵异事件
575698
262620zzj楼主2025/2/3 20:26

编译错误,48行定义mid那里 l was not declared in this scope,但是我其他线段树都是这么写的没报过编译错误啊

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,ll[N],fa[N];
vector<int> q[N];
bool e[N];
int dfn[N],siz[N],idfn[N],dfn_timer;
inline void dfs0(int u){
    dfn[u]=++dfn_timer;
    idfn[dfn_timer]=u;
    siz[u]=1;
    for(int v:q[u])dfs0(v),siz[u]+=siz[v];
}
namespace ZERO{
    set<int> s;
    inline int lowbit(int x){return x&-x;}
    int c[N];
    inline void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
    inline int query(int x){int res=0;for(;x>=1;x-=lowbit(x))res+=c[x];return res;}
    inline int query(int l,int r){return query(r)-query(l-1);}
    inline void init(){
        s.insert(0);
        for(int i=1;i<=n;i++)if(e[i])s.insert(dfn[i]);
        for(int i=1;i<=n;i++)if(!e[i]&&!ll[i])add(c[dfn[i]],1);
    }
    inline void change(int x){
        if(!ll[x])add(dfn[x],e[x]?1:-1);
        if(e[x])s.erase(dfn[x]);
        else s.insert(dfn[x]);
    }
    inline int ask(int x){
        x=dfn[x];
        int y=*s.lower_bound(x);
        return query(y-1)-query(x-1);
    }
}
struct Info{
    int len,sum;
    inline Info(int a=0,int b=0){len=a,sum=b;}
};
inline Info operator + (Info A,Info B){return Info(A.len+B.len,A.sum+B.sum);}
inline Info operator - (Info A,Info B){return Info(A.len-B.len,A.sum-B.sum);}
typedef pair<Info,int> pii;
#define fi first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
namespace ONE{
    constexpr int M=2.5e6;
    int t[N];
    namespace RABBIT{
        int mx[M];
        Info info[M];
        inline Info calc(int p,int l,int r,int lim){
            if(l==r)return mx[p]>=lim?info[p]:Info(0,0);
            if(mx[ls]>=lim)return calc(ls,l,mid,lim)+info[p]-info[ls];
            else return calc(rs,mid+1,r,lim);
        }
        inline void push_up(int p){
            mx[p]=max(mx[ls],mx[rs]);
            info[p]=info[ls]+calc(rs,mid+1,r,mx[ls]);
        }
        inline void build(int p,int l,int r){
            if(l==r)return mx[p]=info[p].sum=t[idfn[l]],info[p].len=1,void();
            build(ls,l,mid);
            build(rs,mid+1,r);
            push_up(p);
        }
        inline void modify(int p,int l,int r,int pos,int val){
            if(l==r)return mx[p]=info[p].sum=val,void();
            if(pos<=mid)modify(ls,l,mid,pos,val);
            else modify(rs,mid+1,r,pos,val);
            push_up(p);
        }
        inline pair<Info,int> query(int p,int l,int r,int L,int R,int lim){
            if(r<L||R<l)return pii(Info(0,0),lim);
            if(L<=l&&r<=R)return pii(calc(p,l,r,lim),max(lim,mx[p]));
            Info res(0,0);
            if(mid>=L){
                pii tmp=query(ls,l,mid,L,R,lim);
                res=res+tmp.fi;
                lim=tmp.se;
            }
            if(mid<R){
                pii tmp=query(rs,mid+1,r,L,R,lim);
                res=res+tmp.fi;
                lim=tmp.se;
            }
            return pii(res,lim);
        }
    }
    int z[N];
    namespace T{
        int mx[M],tag[M];
        inline void build(int p,int l,int r){
            if(l==r)return void(mx[p]=z[idfn[l]]);
            build(ls,l,mid);
            build(rs,mid+1,r);
            mx[p]=max(mx[ls],mx[rs]);
        }
        inline void add(int p,int l,int r,int L,int R,int val){
            if(r<L||R<l)return;
            if(L<=l&&r<=R)return mx[p]+=val,tag[p]+=val,void();
            add(ls,l,mid,L,R,val);
            add(rs,mid+1,r,L,R,val);
            mx[p]=max(mx[ls],mx[rs]);
        }
        inline int query(int p,int l,int r,int L,int R,int s){
            if(r<L||R<l)return -1;
            if(L<=l&&r<=R)return s+mx[p];
            s+=tag[p];
            return max(query(ls,l,mid,L,R,s),query(rs,mid+1,r,L,R,s));
        }
    }
    inline void dfs(int u){
        z[u]=z[fa[u]];
        for(int v:q[u])dfs(v),t[u]=max(t[u],t[v]);
        if(e[u])t[u]++,z[u]++;
    }
    inline void init(){
        dfs(1);
        RABBIT::build(1,1,n);
        T::build(1,1,n);
    }
    inline void change(int x){
        T::add(1,1,n,dfn[x],dfn[x]+siz[x]-1,e[x]?-1:1);//upd array z
        int tx=T::query(1,1,n,dfn[x],dfn[x]+siz[x]-1,0);
        tx-=T::query(1,1,n,dfn[fa[x]],dfn[fa[x]],0);
        RABBIT::modify(1,1,n,dfn[x],tx);
    }
    inline Info ask(int x){
        return RABBIT::query(1,1,n,dfn[x],dfn[x]+siz[x]-1,1).fi;
    }
}
int main(){
    freopen("sleep.in","r",stdin);
    freopen("sleep.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>e[i]>>ll[i];
        for(int j=1,tmp;j<=ll[i];j++){
            cin>>tmp;
            q[i].push_back(tmp);
            fa[tmp]=i;
        }
    }
    dfs0(1);
    ZERO::init();
    ONE::init();
    while(m--){
        int o,k;cin>>o>>k;
        if(o==1){
            ZERO::change(k);
            ONE::change(k);
            e[k]^=1;
        }
        if(o==2){
            int tim=ZERO::ask(k);
            Info omega=ONE::ask(k);
            cout<<tim+omega.sum+(tim+omega.len>=2)<<'\n';
        }
    }
    return 0;
}
2025/2/3 20:26
加载中...