首页 > 代码库 > Codeforces 444C(线段树)
Codeforces 444C(线段树)
区间颜色不一致就更新到底,否则lazy标记
#include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std; #define lc l,m,index<<1 #define rc m+1,r,index<<1|1 #define N 100005 #define ll __int64 struct node { bool same; ll col,sum,add; }seg[N<<2]; ll n,m; void color(ll x,ll add,ll l,ll r,ll index) { seg[index].same=true; seg[index].sum+=add*(r-l+1); seg[index].col=x; seg[index].add+=add; } void pushup(ll l,ll r,ll index) { seg[index].sum=seg[index<<1].sum+seg[index<<1|1].sum; if(seg[index<<1].same&&seg[index<<1|1].same&&seg[index<<1].col==seg[index<<1|1].col) { seg[index].same=true; seg[index].col=seg[index<<1].col; } else seg[index].same=false; } void pushdown(ll l,ll r,ll index) { ll m=(l+r)>>1; if(seg[index].add) { color(seg[index].col,seg[index].add,lc); color(seg[index].col,seg[index].add,rc); seg[index].add=0; } } void build(ll l,ll r,ll index) { ll m=(l+r)>>1; if(l==r) { seg[index].same=true; seg[index].col=l; seg[index].sum=0; return; } build(lc); build(rc); pushup(l,r,index); } void update(ll L,ll R,ll x,ll l,ll r,ll index) { ll m=(l+r)>>1; if(L==l&&R==r&&seg[index].same) { color(x,abs(seg[index].col-x),l,r,index); return; } pushdown(l,r,index); if(R<=m)update(L,R,x,lc); else if(L>m)update(L,R,x,rc); else { update(L,m,x,lc); update(m+1,R,x,rc); } pushup(l,r,index); } ll query(ll L,ll R,ll l,ll r,ll index) { ll m=(l+r)>>1; if(L==l&&R==r)return seg[index].sum; pushdown(l,r,index); if(R<=m)return query(L,R,lc); else if(L>m)return query(L,R,rc); else return query(L,m,lc)+query(m+1,R,rc); } int main() { scanf("%I64d%I64d",&n,&m); build(1,n,1); while(m--) { ll op,a,b,c; scanf("%I64d",&op); if(op==1) { scanf("%I64d%I64d%I64d",&a,&b,&c); update(a,b,c,1,n,1); } else { scanf("%I64d%I64d",&a,&b); printf("%I64d\n",query(a,b,1,n,1)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。