MnZn求助
查看原帖
MnZn求助
231938
Chanter楼主2021/7/26 16:20

赛场看到T1打的动挺高兴,结果调不动kel

然后发现是线段树锅了

然后还是调不动

所以来求教

class Node{
    public:
        int l,r;
        int cnt,dl,dr;
        //dl指左边颜色,dr指右边颜色
        int a;
        //a是延迟标记
        #define l(o) t[o].l
        #define r(o) t[o].r
        #define len(o) (t[o].r-t[o].l+1)
        #define cnt(o) t[o].cnt
        #define dl(o) t[o].dl
        #define dr(o) t[o].dr
        #define a(o) t[o].a
}t[N<<2];
il void spread(int o){//延迟标记下传
    if(!a(o)) return ;
    dl(o<<1)=dr(o<<1)=dl(o<<1|1)=dr(o<<1|1)=a(o);
    cnt(o<<1)=len(o<<1)-1, cnt(o<<1|1)=len(o<<1|1)-1;
    a(o<<1)=a(o<<1|1)=a(o);
    a(o)=0;
}
il int get(int o,int x){//单点颜色查询
    if(l(o)==r(o)) return dl(o);
    spread(o);
    int mid(l(o)+r(o)>>1);
    if(x<=mid) return get(o<<1,x);
    return get(o<<1|1,x);
}
il void init(int o){//更新当前信息
    dl(o)=dl(o<<1),dr(o)=dr(o<<1|1);
    cnt(o)=cnt(o<<1)+cnt(o<<1|1);
    if(dr(o<<1) and dr(o<<1)==dl(o<<1|1)) ++cnt(o);
}
il void build(int o,int l,int r){//建树
    l(o)=l, r(o)=r, dl(o)=dr(o)=cnt(o)=0;
    if(l==r) return ;
    int mid(l+r>>1);
    build(o<<1,l,mid), build(o<<1|1,mid+1,r);
}
il void Recover(int o,int l,int r,int v){//区间推平
    if(l<=l(o) and r(o)<=r) return cnt(o)=len(o)-1, dl(o)=dr(o)=a(o)=v, void();
    spread(o);
    int mid(l(o)+r(o)>>1);
    if(l<=mid) Recover(o<<1,l,r,v);
    if(r>mid) Recover(o<<1|1,l,r,v);
    init(o);
}
il int ask(int o,int l,int r){//区间查询,相邻颜色相同 的数量
    if(l<=l(o) and r(o)<=r) return cnt(o);
    spread(o);
    int mid(l(o)+r(o)>>1);
    int ans(0);
    if(l<=mid) ans+=ask(o<<1,l,r);
    if(r>mid) ans+=ask(o<<1|1,l,r);
    if(l<=mid and r>mid) ans+=(dr(o<<1)==dl(o<<1|1));
    return ans;
}
2021/7/26 16:20
加载中...