赛场看到T1打的动挺高兴,结果调不动
然后发现是线段树锅了
然后还是调不动
所以来求教
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;
}