xiaozhichen123 @ 2024-11-16 20:14:33
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a[10000001], b[10000001], x, k, y, q, ans, c[100000001];
void tree(int l, int r, int x) {
if (l < r) { //还能继续二分建树
int mid = l + (r - l) / 2; //讲数据分成两份，放在节点的左下节点和右下节点
tree(l, mid, x * 2); //节点的左下节点处继续分
tree(mid + 1, r, x * 2 + 1); //节点的右下节点处继续分
b[x] = b[x * 2] + b[x * 2 + 1]; //递归回来后x节点的值为子节点的值的和 所有子节点的区间和
} else {
b[x] = a[l]; //叶节点赋值
}
}
int inquire(int ll, int rr, int l, int r, int x) { //查询
int mid = ll + (rr - ll) / 2;
if (c[x] != 0) { //此节点有lazy
int sum = rr - ll + 1; //求区间的范围，以用来的整个区间所得的和
b[x] += sum * c[x]; //此区间所得的和等于所有包含节点的个数*每个节点所加的数
c[x * 2] = c[x * 2 + 1] = c[x]; //将lazy标记向下传递
c[x] = 0; //清除lazy标记
}
if (ll == l && rr == r) { //当查到要查的区间时返回
return b[x];
}
if (r <= mid) { //当区间全在左边时只继续查左边 注意：“<=”是因为mid的位置在左边
return inquire(ll, mid, l, r, x * 2); //继续查左边
}
if (l > mid) { //当区间全在右边时只继续查右边 注意:“>”是因为mid的位置在左边
return inquire(mid + 1, rr, l, r, x * 2 + 1); //继续查右边
}
if (r > mid && l <= mid) { //当区间部分在左，部分在右时，即mid在区间内，既要查左边，又要查右边
return inquire(ll, mid, l, mid, x * 2) + inquire(mid + 1, rr, mid + 1, r, x * 2 + 1); //左边的区间和加右边的区间和
}
}
void pplus(int ll, int rr, int l, int r, int x, int num) { //区间加法(实际上只是加上lazy标记)
int mid = ll + (rr - ll) / 2;
b[x] += (r - l + 1) * num;
if (ll == l && rr == r) { //区间完全重合
c[x * 2+1] += num;
c[x * 2] += num; //lazy标记赋值
} else if (r <= mid) {
pplus(ll, mid, l, r, x * 2, num); //向左查找
} else if (l > mid) {
return pplus(mid + 1, rr, l, r, x * 2 + 1, num); //向右查找
} else if (r > mid && l <= mid) { //分割向两边查找
pplus(ll, mid, l, mid, x * 2, num);
pplus(mid + 1, rr, mid + 1, r, x * 2 + 1, num);
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
tree(1, n, 1);
for (int i = 1; i <= m; i++) {
cin >> q;
//cout << endl;
// cout << endl;
if (q == 2) {
cin >> x >> y;
//cout << endl;
cout << inquire(1, n, x, y, 1) << endl; //进入查询
}
if (q == 1) {
cin >> x >> y >> k;
pplus(1, n, x, y, 1, k); //进入加法
}
// int m = 1;
// cout << endl;
// cout << endl;
// for (int i = 1; i <= 9; i++) {
// if (i == m * 2) {
// cout << endl;
// m = i;
// }
// cout << b[i] << " " << c[i] << " ";
// }
// cout << endl;
// cout << endl;
}
}by __Refine__ @ 2024-11-16 20:37:40
if (ll == l && rr == r) { //区间完全重合应改为
if (ll >= l && rr <= r) { //区间完全重合因为包含时也要返回
by xiaozhichen123 @ 2024-11-19 19:27:35
@loserli 赋值懒标记也需要时刻返回吗？
by __Refine__ @ 2024-11-19 20:25:58
@xiaozhichen123不用
by __Refine__ @ 2024-11-19 20:27:40
改好了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, a[10000001], b[10000001], x, k, y, q, ans, c[100000001];
void tree(int l, int r, int x) {
if (l < r) {
int mid = l + (r - l) / 2;
tree(l, mid, x * 2);
tree(mid + 1, r, x * 2 + 1);
b[x] = b[x * 2] + b[x * 2 + 1];
} else {
b[x] = a[l];
}
}
int inquire(int ll, int rr, int l, int r, int x) {
int mid = ll + (rr - ll) / 2;
if (c[x] != 0) {
int sum = rr - ll + 1;
b[x] += sum * c[x];
c[x * 2]+=c[x];
c[x * 2 + 1] += c[x]; //不能赋值，可能不为零
c[x] = 0;
}
if (ll == l && rr == r) {
return b[x];
}
if (r <= mid) {
return inquire(ll, mid, l, r, x * 2);
}
if (l > mid) {
return inquire(mid + 1, rr, l, r, x * 2 + 1);
}
if (r > mid && l <= mid) {
return inquire(ll, mid, l, mid, x * 2) + inquire(mid + 1, rr, mid + 1, r, x * 2 + 1);
}
}
void pplus(int ll, int rr, int l, int r, int x, int num) {
int mid = ll + (rr - ll) / 2;
b[x] += (r - l + 1) * num;
if (c[x] != 0) { //需要下传
int sum = rr - ll + 1;
b[x] += sum * c[x];
c[x * 2]+=c[x];
c[x * 2 + 1] += c[x];//同上
c[x] = 0;
}
if (ll == l && rr == r) {
c[x * 2+1] += num;
c[x * 2] += num;
} else if (r <= mid) {
pplus(ll, mid, l, r, x * 2, num);
} else if (l > mid) {
return pplus(mid + 1, rr, l, r, x * 2 + 1, num);
} else if (r > mid && l <= mid) {
pplus(ll, mid, l, mid, x * 2, num);
pplus(mid + 1, rr, mid + 1, r, x * 2 + 1, num);
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
tree(1, n, 1);
for (int i = 1; i <= m; i++) {
cin >> q;
//cout << endl;
// cout << endl;
if (q == 2) {
cin >> x >> y;
//cout << endl;
cout << inquire(1, n, x, y, 1) << endl; //进入查询
}
if (q == 1) {
cin >> x >> y >> k;
pplus(1, n, x, y, 1, k); //进入加法
}
// int m = 1;
// cout << endl;
// cout << endl;
// for (int i = 1; i <= 9; i++) {
// if (i == m * 2) {
// cout << endl;
// m = i;
// }
// cout << b[i] << " " << c[i] << " ";
// }
// cout << endl;
// cout << endl;
}
}看在调了1h的份上，能给个关注吗:)
by __Refine__ @ 2024-11-19 20:29:39
另外线段树写的不熟练时可以把标记下传写成函数，比如:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,sum[400001],a[100001],add[400001];
inline void da(int l,int r,int k,int z)
{
add[k]+=z;
sum[k]+=z*(r-l+1);
}
inline void xia(int l,int r,int k,int mid)
{
if(add[k]==0) return ;
da(l,mid,k<<1,add[k]);
da(mid+1,r,(k<<1)|1,add[k]);
add[k]=0;
}
void build(int l,int r,int k)
{
if(l==r)
{
sum[k]=a[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,(k<<1)|1);
sum[k]=sum[k<<1]+sum[(k<<1)|1];
}
int query(int l,int r,int k,int x,int y)
{
if(l>=x&&r<=y)
{
return sum[k];
}
int mid=(l+r)>>1;
xia(l,r,k,mid);
int ans=0;
if(x<=mid)ans+=query(l,mid,k<<1,x,y);
if(y>mid)ans+=query(mid+1,r,(k<<1)|1,x,y);
sum[k]=sum[k<<1]+sum[k<<1|1];
return ans;
}
void update(int l,int r,int k,int x,int y,int z)
{
if(l>=x&&r<=y)
{
da(l,r,k,z);
return ;
}
int mid=(l+r)>>1;
xia(l,r,k,mid);
if(x<=mid)update(l,mid,k<<1,x,y,z);
if(y>mid)update(mid+1,r,(k<<1)|1,x,y,z);
sum[k]=sum[k<<1]+sum[(k<<1)|1];
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int x,y,z,k;
scanf("%d%d%d",&x,&y,&z);
if(x==1)
{
scanf("%d",&k);
update(1,n,1,y,z,k);
}
else
{
cout<<query(1,n,1,y,z)<<endl;
}
}
return 0;
}by __Refine__ @ 2024-11-19 20:32:06
似乎已经关了
by xiaozhichen123 @ 2024-11-20 16:05:03
@loserli
是的，谢谢
by xiaozhichen123 @ 2024-11-20 16:06:05
@loserli
太谢谢了
by __Refine__ @ 2024-11-21 20:24:48
呃
by __Refine__ @ 2024-11-21 20:25:55
tree(1,mid,x*2);
tree(mid+1,r,x*2+1);改为
tree(l,mid,x*2);
tree(mid+1,r,x*2+1);