60分 估计是数据范围的问题

P3372 【模板】线段树 1

[测试点4的数据](https://www.luogu.com.cn/paste/jl0gwu32)和我输出的后面一些是一样的 应该不会访问修改10000次还能偶然对吧
by _8008008 @ 2023-09-07 18:28:25


首先,你的数组开小了,最好是 N=1e5+5 ,然后 add 函数里最后几行应该加 else ```cpp inline void add(int num,int k){ int l=tree[num].l,r=tree[num].r,mid=(l+r)/2; if(ans_r<l||r<ans_l)return; if(ans_l<=l&&ans_r>=r){ tree[num].lazy+=k; return; } if(ans_l<=mid)add(num*2,k); if(ans_r>=mid+1)add(num*2+1,k); if(ans_l>=l&&ans_r<r)tree[num].sum+=(ans_r-ans_l+1)*k; else if(ans_l<=l&&ans_r<r)tree[num].sum+=(ans_r-l+1)*k; else if(ans_r>=r&&l<ans_l)tree[num].sum+=(r-ans_l+1)*k; } ```
by sjr3065335594 @ 2023-09-07 18:36:25


而且你的线段树码风过于奇怪,可能对于之后些别的东西不太方便改,你可以看看别的人写的线段树
by sjr3065335594 @ 2023-09-07 18:38:39


@[sjr3065335594](/user/564883) 不是 是我大小于号写反了 终于过了 好兴奋 ~~还有我的码风很奇怪吗~~ 那几行试过加```else```如果正确的话 他们是不会有重叠的 和加```else```效果一样 ``` if(ans_l<=mid)add(num*2,k); if(ans_r>=mid+1)add(num*2+1,k); if(ans_l>=l&&ans_r<r)tree[num].sum+=(ans_r-ans_l+1)*k; else if(ans_l<=l&&ans_r<r)tree[num].sum+=(ans_r-l+1)*k; else if(ans_r>=r&&l<ans_l)tree[num].sum+=(r-ans_l+1)*k; ``` 改为 ``` if(ans_l<=mid)add(num*2,k); if(ans_r>=mid+1)add(num*2+1,k); if(ans_l>l&&ans_r<r)tree[num].sum+=(ans_r-ans_l+1)*k; if(ans_l<=l&&ans_r<r)tree[num].sum+=(ans_r-l+1)*k; if(ans_r>=r&&l<ans_l)tree[num].sum+=(r-ans_l+1)*k; ``` 即可
by _8008008 @ 2023-09-07 19:27:27


@[_8008008](/user/803885) 但是我加了 else 就过了
by sjr3065335594 @ 2023-09-07 19:39:34


不过你的码风真的很奇怪,至少跟别人写的都不一样,就很难让别人看懂,因为你没写 pushdown 而是直接在修改和查询计算 lazytag 就很奇怪
by sjr3065335594 @ 2023-09-07 19:40:55


同分同样例没过求改: ``` #include<bits/stdc++.h> using namespace std; int n,m,zl,x,y,k; long long xds[400005],a[400005],lb[400005]; long long js(int l,int r,int w) { if(l==r)return xds[w]=a[l]; int mid=(l+r)/2; return xds[w]=js(l,mid,w*2)+js(mid+1,r,w*2+1); } long long cz(int l,int r,int ml,int mr,int w) { if(l==r) { xds[w]+=lb[w]; lb[w]=0; return xds[w]; } int mid=(l+r)/2; long long ans=0; lb[w*2]+=lb[w]; lb[w*2+1]+=lb[w]; xds[w]+=lb[w]*(r-l+1); lb[w]=0; if(l>=ml&&r<=mr)return xds[w]; if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))ans+=cz(l,mid,ml,mr,w*2); if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))ans+=cz(mid+1,r,ml,mr,w*2+1); return ans; } void zj(int l,int r,int ml,int mr,int w,int k) { if(l==r) { if(l>=ml&&l<=mr) { lb[w]+=k; } return; } int mid=(l+r)/2; long long ans=0; lb[w*2]+=lb[w]; lb[w*2+1]+=lb[w]; xds[w]+=lb[w]*(r-l+1); lb[w]=0; if(l<=ml&&r>=mr)xds[w]+=k*(mr-ml+1); else if(l<=ml&&r<=mr)xds[w]+=max(0,r-ml+1)*k; else if(l>=ml&&r>=mr)xds[w]+=max(0,mr-l+1)*k; else { lb[w]=k; return; } if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))zj(l,mid,ml,mr,w*2,k); if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))zj(mid+1,r,ml,mr,w*2+1,k); return; } int main () { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; js(1,n,1); while(m--) { cin>>zl>>x>>y; if(zl==1) { cin>>k; zj(1,n,x,y,1,k); } else cout<<cz(1,n,x,y,1)<<"\n"; } } ```
by lijunxi1 @ 2023-10-04 22:43:07


|