Coding_Zzh @ 2023-03-24 19:03:25
#include<cstdio>
#include<iostream>
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int MAXN = 5e5 + 10;
int n, m;
int a[MAXN];
struct tree
{
int l, r, sum, add;
} t[MAXN << 2];
void push_down(int p)
{
if(t[p].add)
{
t[lc].sum += (t[lc].r - t[lc].l + 1) * t[p].add;
t[rc].sum += (t[rc].r - t[rc].l + 1) * t[p].add;
t[lc].add += t[p].add;
t[rc].add += t[p].add;
t[p].add = 0;
}
}
void build(int p, int l, int r)
{
t[p] = {l, r, a[l], 0};
if(l == r) return;
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid+1, r);
t[p].sum = t[lc].sum + t[rc].sum;
}
void updata(int p, int x, int k)
{
if(t[p].l == x && t[p].r == x)
{
t[p].sum += k;
return;
}
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
if(x <= mid) updata(lc, x, k);
if(x > mid) updata(rc, x, k);
t[p].sum = t[lc].sum + t[rc].sum;
}
void add(int p, int x, int y, int k)
{
if(x <= t[p].l && t[p].r <= y)
{
t[p].sum += (t[p].r - t[p].l + 1) * k;
t[p].add += k;
return;
}
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
push_down(p);
if(x <= mid) add(lc, x, y, k);
if(y > mid) add(rc, x, y, k);
t[p].sum = t[lc].sum + t[rc].sum;
}
int query(int p, int x, int y)
{
if(x <= t[p].l && t[p].r <= y)
return t[p].sum;
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
int sum = 0;
if(x <= mid) sum += query(lc, x, y);
if(y > mid) sum += query(rc, x, y);
return sum;
}
int main()
{
scanf("%d %d", &n, &m);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
build(1, 1, n);
while(m--)
{
int op;
scanf("%d", &op);
if(op == 1)
{
int x, y ,k;
scanf("%d %d %d", &x, &y, &k);
//updata(1, x, y, k);
add(1, x, y, k);
}
else
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", query(1, x, y));
}
}
return 0;
}by Coding_Zzh @ 2023-03-24 19:03:45
全wa
by Coding_Zzh @ 2023-03-24 19:04:44
在树状数组1上改动了add和push_down而已
by OldDriverTree @ 2023-03-24 19:20:27
@Coding_Zzh query 中还要 push_down
by Coding_Zzh @ 2023-03-24 19:35:51
#include<cstdio>
#include<iostream>
#define unsigned long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int MAXN = 1000010;
int n, m;
int a[MAXN];
struct tree
{
int l, r, sum, add;
} t[MAXN << 2];
void push_down(int p)
{
if(t[p].add)
{
t[lc].sum += (t[lc].r - t[lc].l + 1) * t[p].add;
t[rc].sum += (t[rc].r - t[rc].l + 1) * t[p].add;
t[lc].add += t[p].add;
t[rc].add += t[p].add;
t[p].add = 0;
}
}
void build(int p, int l, int r)
{
t[p] = {l, r, a[l], 0};
if(l == r) return;
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid+1, r);
t[p].sum = t[lc].sum + t[rc].sum;
}
void updata(int p, int x, int k)
{
if(t[p].l == x && t[p].r == x)
{
t[p].sum += k;
return;
}
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
if(x <= mid) updata(lc, x, k);
if(x > mid) updata(rc, x, k);
t[p].sum = t[lc].sum + t[rc].sum;
}
void add(int p, int x, int y, int k)
{
if(x <= t[p].l && t[p].r <= y)
{
t[p].sum += (t[p].r - t[p].l + 1) * k;
t[p].add += k;
return;
}
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
push_down(p);
if(x <= mid) add(lc, x, y, k);
if(y > mid) add(rc, x, y, k);
t[p].sum = t[lc].sum + t[rc].sum;
}
int query(int p, int x, int y)
{
if(x <= t[p].l && t[p].r <= y)
return t[p].sum;
int l = t[p].l, r = t[p].r;
int mid = l + r >> 1;
int sum = 0;
push_down(p);
if(x <= mid) sum += query(lc, x, y);
if(y > mid) sum += query(rc, x, y);
return sum;
}
signed main()
{
scanf("%d %d", &n, &m);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
build(1, 1, n);
while(m--)
{
int op;
scanf("%d", &op);
if(op == 1)
{
int x, y ,k;
scanf("%d %d %d", &x, &y, &k);
//updata(1, x, y, k);
add(1, x, y, k);
}
else
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", query(1, x, y));
}
}
return 0;
}query中加了push_down,立马70pts,后三点wa,原以为是数据类型的问题，按照题解大小去修改还是无果 请求大佬求助@guoxiangyu66
by ben090302 @ 2023-03-25 16:07:28
@Coding_Zzh 没开long long