O口O……
by Kan_kiz @ 2019-04-09 21:38:26
query zha le
by Froggy @ 2019-04-09 22:04:31
return q(lsx,L,R)+q(rs,L,R)
by Froggy @ 2019-04-09 22:05:48
@[万岁小姐姐](/space/show?uid=88686)
by Froggy @ 2019-04-09 22:05:55
@[Froggy](/space/show?uid=100285)
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int a[maxn],n,m;
struct node{int l,r;int val,add;}tree[maxn*4];
int ls(int x){return x*2;}
int rs(int x){return x*2+1;}
void push_up(int x){tree[x].val=tree[ls(x)].val+tree[rs(x)].val;}
void push_down(int x)
{
if(tree[x].add)
{
tree[ls(x)].val+=tree[x].add*(tree[ls(x)].r-tree[ls(x)].l+1);
tree[rs(x)].val+=tree[x].add*(tree[rs(x)].r-tree[rs(x)].l+1);
tree[ls(x)].add+=tree[x].add;
tree[rs(x)].add+=tree[x].add;
tree[x].add=0;
}
}
void build(int p,int L,int R)
{
tree[p].l=L;tree[p].r=R;
tree[p].add=0;
if(L==R){tree[p].val=a[L];return;}
int mid=(L+R)>>1;
build(ls(p),L,mid);
build(rs(p),mid+1,R);
push_up(p);
}
void update(int p,int L,int R,int k)
{
if(L<=tree[p].l&&tree[p].r<=R)
{
tree[p].val+=(int)k*(tree[p].r-tree[p].l+1);
tree[p].add+=k;
return;
}
push_down(p);
int mid=(tree[p].l+tree[p].r)>>1;
if(L<=mid)update(ls(p),L,R,k);
if(R>mid) update(rs(p),L,R,k);
push_up(p);
}
int query(int p,int L,int R)
{
if(R<tree[p].l||L>tree[p].r)return 0;
//printf("%d %d %d\n",p,L,R);
if(L<=tree[p].l&&tree[p].r<=R)return tree[p].val;
push_down(p);
int mid=(tree[p].l+tree[p].r)>>1;
return query(ls(p),L,R)+query(rs(p),L,R);
}
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 q,x,y,z;
scanf("%d",&q);
if(q==1)
{
scanf("%d%d%d",&x,&y,&z);
update(1,x,y,z);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",query(1,x,y));
}
}
}
```
WA》》
by Shirο @ 2019-04-10 20:59:50
没开浪浪见祖宗
by Froggy @ 2019-04-11 11:47:32
@[万岁小姐姐](/space/show?uid=88686)
by Froggy @ 2019-04-11 11:47:36
全开
by Froggy @ 2019-04-11 11:47:47