Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 死活过不了 求纠正

Posted by blossomQAQ at 2017-08-12 22:09:35 on Problem 3468
```#include<iostream>
#include<stdio.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

struct tree
{
LL sum;
LL laz;
int l, r;
};

tree segtree[MAXN<<2];

void build(int rt, int l, int r)
{
segtree[rt].l = l;
segtree[rt].r = r;
segtree[rt].laz = 0;
if(l == r)
{
scanf("%lld", &segtree[rt].sum);
return ;
}
int mid = (l + r) >> 1;
build(rt<<1, l, mid);
build(rt<<1|1, mid + 1, r);
segtree[rt].sum = (segtree[rt<<1].sum + segtree[rt<<1|1].sum);
}

void pushdown(int rt, int dis)
{
if(segtree[rt].laz)
{
segtree[rt<<1].laz+=segtree[rt].laz;
segtree[rt<<1|1].laz+=segtree[rt].laz;
segtree[rt<<1].sum+=segtree[rt].laz * (dis - (dis>>1));
segtree[rt<<1|1].sum+=segtree[rt].laz * (dis>>1);
segtree[rt].laz = 0;
}
}

void update(int rt, int l, int r, int c)
{
if(segtree[rt].l == l && segtree[rt].r == r)
{
segtree[rt].laz+=c;
segtree[rt].sum+=c * (r - l + 1);
return ;
}
if(segtree[rt].l == segtree[rt]. r)
return ;
pushdown(rt, segtree[rt].r - segtree[rt].l + 1);
int mid = (segtree[rt].l + segtree[rt].r)>>1;
if(r<=mid)
update(rt<<1, l, r, c);
else if(l>mid)
update(rt<<1|1, l, r, c);
else
{
update(rt<<1, l, mid, c);
update(rt<<1|1, mid + 1, r, c);
}
segtree[rt].sum = segtree[rt<<1].sum + segtree[rt<<1|1].sum;
}

LL query(int rt, int l, int r)
{
LL s = 0;
if(segtree[rt].l == l && segtree[rt].r == r)
return segtree[rt].sum;
pushdown(rt, r - l + 1);
int mid = (segtree[rt].l + segtree[rt].r)>>1;
if(r<=mid)
s+=query(rt<<1, l, r);
else if(l>mid)
s+=query(rt<<1|1, l, r);
else
{
s+=query(rt<<1, l, mid);
s+=query(rt<<1|1, mid + 1, r);
}
return s;
}

int main()
{
int n, q;
while(scanf("%d%d", &n , &q)!=EOF)
{
build(1, 1, n);
int l, r, c;
char ch[5];
while(q--)
{
scanf("%s", ch);
if(ch[0] == 'C')
{
scanf("%d%d%d", &l, &r, &c);
update(1, l, r, c);
}
else if(ch[0] == 'Q')
{
scanf("%d%d", &l, &r);
LL s = query(1, l, r);
printf("%lld\n", s);
}

}
}
return 0;
}```

Followed by: