一道线段树板题
为啥困难我也不知道qwq
代码如下:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int N=100010;
int n,m;
int a[N];
struct MS{
int l,r,len;
ll sum,lazy;
}t[8000000];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].len=r-l+1;
if(l==r)
{
t[p].sum=a[l];
return;
}
build(p*2,l,(l+r)/2);
build(p*2+1,(l+r)/2+1,r);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void pd(int p)
{
if(t[p].lazy)
{
t[p*2].lazy+=t[p].lazy;
t[p*2+1].lazy+=t[p].lazy;
t[p*2].sum+=t[p*2].len*t[p].lazy;
t[p*2+1].sum+=t[p*2+1].len*t[p].lazy;
t[p].lazy=0;
}
}
void add(int p,int l,int r,int x)
{
if(l<=t[p].l&&r>=t[p].r)
{
t[p].sum+=x*t[p].len;
t[p].lazy+=x;
return;
}
pd(p);
int mid=(t[p].l+t[p].r)/2;
if(l<=mid)add(p*2,l,r,x);
if(r>mid)add(p*2+1,l,r,x);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
ll ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
pd(p);
ll ans=0;
int mid=(t[p].l+t[p].r)/2;
if(l<=mid)ans+=ask(p*2,l,r);
if(r>mid)ans+=ask(p*2+1,l,r);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
string op;
int l,r,x;
cin>>op;
if(op[0]=='Q')
{
scanf("%d%d",&l,&r);
printf("%lld\n",ask(1,l,r));
}
else
{
scanf("%d%d%d",&l,&r,&x);
add(1,l,r,x);
}
}
}
MS tql!%%%%%%%%%%%%%%%%%%
orz
%%%%%%%%%%
orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
orz
orz
# stO Orz
orz