セグメントツリー区間lazyタグ大法の修正
1997 ワード
#include
#include
#define maxn 100000 + 10
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
struct Node
{
int sum, lazy;
} T[maxn<<2];
void PushUp(int rt)
{
T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum;
}
void PushDown(int L, int R, int rt)
{
int mid = (L + R) >> 1;
T[rt<<1].sum = T[rt].lazy * (mid - L + 1);
T[rt<<1|1].sum = T[rt].lazy * (R - mid);
T[rt<<1].lazy = T[rt].lazy;
T[rt<<1|1].lazy = T[rt].lazy;
T[rt].lazy = 0;
}
void Build(int L, int R, int rt)
{
if(L == R)
{
scanf("%d", &T[rt].sum);
return ;
}
int mid = (L + R) >> 1;
Build(Lson);
Build(Rson);
PushUp(rt);
}
void Update(int l, int r, int v, int L, int R, int rt)
{
if(l==L && r==R)
{
T[rt].lazy = v;
T[rt].sum = v * (R - L + 1);
return ;
}
int mid = (L + R) >> 1;
if(T[rt].lazy) PushDown(L, R, rt);
if(r <= mid) Update(l, r, v, Lson);
else if(l > mid) Update(l, r, v, Rson);
else
{
Update(l, mid, v, Lson);
Update(mid+1, r, v, Rson);
}
PushUp(rt);
}
int Query(int l, int r, int L, int R, int rt)
{
if(l==L && r== R)
return T[rt].sum;
int mid = (L + R) >> 1;
if(T[rt].lazy) PushDown(L, R, rt);
if(r <= mid) return Query(l, r, Lson);
else if(l > mid) return Query(l, r, Rson);
return Query(l, mid, Lson) + Query(mid + 1, r, Rson);
}
int main()
{
int n, q;
scanf("%d", &n);
Build(1, n, 1);
scanf("%d", &q);
int a, b, c, d;
while(q--)
{
scanf("%d%d%d", &a, &b, &c);
if(a)
{
scanf("%d", &d);
Update(b, c, d, 1, n, 1);
}
else printf("%d
", Query(b, c, 1, n, 1));
}
return 0;
}