_8008008 @ 2023-09-07 18:07:21
好像没有人是我这种情况(评测记录)
#include<iostream>
#define int long long
using namespace std;
const int N =10000;
struct node{
int l,r,sum,lazy;
};
int a[N],n,q;node tree[5*N];
inline int build(int num,int l,int r){
tree[num].l=l;tree[num].r=r;
if(l==r){
tree[num].sum=a[l];
return tree[num].sum;
}
int mid=(l+r)/2;
tree[num].sum=build(num*2,l,mid)+build(num*2+1,mid+1,r);
return tree[num].sum;
}
int ans_l,ans_r;
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;
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;
}
inline int sum(int num){
int l=tree[num].l,r=tree[num].r,mid=(l+r)/2,ans=0;
if(ans_l<=l&&ans_r>=r){
return tree[num].sum+(r-l+1)*(tree[num].lazy);
}
if(tree[num].lazy!=0){
tree[num*2].lazy+=tree[num].lazy;
tree[num*2+1].lazy+=tree[num].lazy;
tree[num].sum+=(r-l+1)*(tree[num].lazy);
tree[num].lazy=0;
}
if(ans_l<=mid)ans+=sum(num*2);
if(ans_r>=mid+1)ans+=sum(num*2+1);
return ans;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(q--){
int moss;cin>>moss;
cin>>ans_l>>ans_r;
if(moss==1){
int k;cin>>k;
add(1,k);
}else{
cout<<sum(1)<<endl;
}
}
return 0;
}by _8008008 @ 2023-09-07 18:28:25
测试点4的数据和我输出的后面一些是一样的 应该不会访问修改10000次还能偶然对吧
by sjr3065335594 @ 2023-09-07 18:36:25
首先，你的数组开小了，最好是 N=1e5+5 ，然后 add 函数里最后几行应该加 else
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:38:39
而且你的线段树码风过于奇怪，可能对于之后些别的东西不太方便改，你可以看看别的人写的线段树
by _8008008 @ 2023-09-07 19:27:27
@sjr3065335594 不是 是我大小于号写反了 终于过了 好兴奋 还有我的码风很奇怪吗
那几行试过加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 sjr3065335594 @ 2023-09-07 19:39:34
@_8008008 但是我加了 else 就过了
by sjr3065335594 @ 2023-09-07 19:40:55
不过你的码风真的很奇怪，至少跟别人写的都不一样，就很难让别人看懂，因为你没写 pushdown 而是直接在修改和查询计算 lazytag 就很奇怪
by lijunxi1 @ 2023-10-04 22:43:07
同分同样例没过求改：
#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";
}
}