Laugh_at_the_sky @ 2024-08-16 14:05:30
#include <map>
#include <set>
#include <list>
#include <regex>
#include <queue>
#include <limits>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m;
int a[N];
struct Node {
int l, r;
int sum;
int tag;
};
Node operator + (const Node& a, const Node& b) {
Node x;
x.l = a.l;
x.r = b.r;
x.sum = a.sum + b.sum;
return x;
}
Node t[N << 1 << 1];
void build(int l, int r, int rt) {
if (l == r) {
t[rt].l = t[rt].r = l;
t[rt].sum = a[l];
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
t[rt] = t[rt << 1] + t[rt << 1 | 1];
}
void color(int rt, int x) {
t[rt].sum += (t[rt].r - t[rt].l + 1) * x;
t[rt].tag += x;
}
void color_son(int rt) {
if (t[rt].tag) {
color(rt << 1, t[rt].tag);
color(rt << 1 | 1, t[rt].tag);
t[rt].tag = 0;
}
}
Node query(int l, int r, int rt, int nl, int nr) {
if (l >= nl && r <= nr)
return t[rt];
color_son(rt);
int m = (l + r) >> 1;
if (nl <= m) {
if (m < nr)
return query(l, m, rt << 1, nl, nr) + query(m + 1, r, rt << 1 | 1, nl, nr);
else
return query(l, m, rt << 1, nl, nr);
}
else
return query(m + 1, r, rt << 1 | 1, nl, nr);
}
void update(int l, int r, int rt, int nl, int nr, int x) {
if (l >= nl && r <= nr) {
color(rt, x);
return;
}
color_son(rt);
int m = (l + r) >> 1;
if (nl <= m) update(l, m, rt << 1, nl, nr, x);
if (nr > m) update(m + 1, r, rt << 1 | 1, nl, nr, x);
t[rt] = t[rt << 1] + t[rt << 1 | 1];
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, n, 1);
while (m--) {
int op;
cin >> op;
int x, y;
cin >> x >> y;
if (op == 1) {
int k;
cin >> k;
update(1, n, 1, x, y, k);
}
if (op == 2)
cout << query(1, n, 1, x, y).sum << "\n";
}
return 0;
}
by Laugh_at_the_sky @ 2024-08-16 14:07:47
样例过了，下载的第一个测试点的数据也过了，但就是 WA。
by cqbzpyl @ 2024-08-16 14:21:14
@Laugh_at_the_sky build()里面，把
t[p].l=l,t[p].r=r;
放 if 外面去
by Laugh_at_the_sky @ 2024-08-16 14:26:00
void build(int l, int r, int rt) {
t[rt].l = l;
t[rt].r = r;
if (l == r) {
t[rt].sum = a[l];
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
t[rt] = t[rt << 1] + t[rt << 1 | 1];
}
这样？
by Laugh_at_the_sky @ 2024-08-16 14:26:11
@cqbzpyl
by cqbzpyl @ 2024-08-16 14:26:19
@Laugh_at_the_sky 餐烤代码
#include<bits/stdc++.h>
using namespace std;
int a[1000010],n,d;
struct node{
int l,r;
long long sum,add;
}t[4000010];
void build(int p,int l,int r){//建树
t[p].l=l,t[p].r=r;
if(l==r){
t[p].sum=a[l];
return;
}
int tm=(l+r)>>1;
build(p<<1,l,tm);
build(p<<1|1,tm+1,r);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void spread(int p){
if(t[p].add){
t[p<<1].sum+=t[p].add*(t[p<<1].r-t[p<<1].l+1);
t[p<<1|1].sum+=t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1);
t[p<<1].add+=t[p].add;
t[p<<1|1].add+=t[p].add;
t[p].add=0;
}
}
void change(int p,int l,int r,int d){//
if(l<=t[p].l&&t[p].r<=r){
t[p].sum+=(long long)d*(t[p].r-t[p].l+1);
t[p].add+=d;
return;
}
spread(p);
int tm=(t[p].l+t[p].r)>>1;
if(l<=tm)
change(p<<1,l,r,d);
if(r>tm)
change(p<<1|1,l,r,d);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
long long ask(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r)
return t[p].sum;
spread(p);
int tm=(t[p].l+t[p].r)>>1;
long long val=0;
if(l<=tm)
val+=ask(p<<1,l,r);
if(r>tm)
val+=ask(p<<1|1,l,r);
return val;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int Q,op,x,y;
cin>>n>>Q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(Q--){
cin>>op;
cin>>x>>y;
if(op==1){
cin>>d;
change(1,x,y,d);
}else
cout<<ask(1,x,y)<<endl;
}
return 0;
}球馆 qwq
by fang20081114 @ 2024-08-16 14:42:53
还有query返回值逻辑上有点问题，如果m不在[nl,nr]区间内应该返回0
by Laugh_at_the_sky @ 2024-08-16 14:53:33
为啥在结构体里加上
Node() {
l = r = sum = tag = 0;
}就能 AC？
by cqbzpyl @ 2024-08-16 14:56:33
@Laugh_at_the_sky 不知道
by cqbzpyl @ 2024-08-16 14:57:10
@Laugh_at_the_sky 但理论上不能 AC，rp 问题
by cqbzpyl @ 2024-08-16 15:00:20
这还是我学的线段树吗