wikioi1082【线段树练习 3 】

时间:2022-01-11 02:55:47

题目描述 Description

给你N个数,有两种操作:

1:给区间[a,b]的所有数增加X

2:询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n,接下来n行n个整数,

再接下来一个正整数Q,每行表示操作的个数,

如果第一个数是1,后接3个正整数,

表示在区间[a,b]内每个数增加X,如果是2,

表示操作2询问区间[a,b]的和是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

如题目所示……线段树水到不能再水了……

因为发现这种水题还没过就顺手敲了个

结果因为没开long long就5连wa……真是

#include<cstdio>
#define maxn 1000000
struct treenode{
int l,r,ls,rs,add;
long long tot;
}tree[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}int n,m,treesize;
long long ans;
int a[200001];
inline void update(int k)
{tree[k].tot=tree[tree[k].ls].tot+tree[tree[k].rs].tot;}
inline void downput(int k)
{
int l=tree[k].l,r=tree[k].r,toadd=tree[k].add;
tree[k].add=0;
int len=r-l+1;
if (len==1){tree[k].tot+=tree[k].add;return;}
tree[tree[k].ls].tot+=(long long)toadd*(len-(len>>1));
tree[tree[k].ls].add+=toadd;
tree[tree[k].rs].tot+=(long long)toadd*(len>>1);
tree[tree[k].rs].add+=toadd;
update(k);
}
inline void buildtree(int l,int r)
{
if (l>r) return;
int now=++treesize;
tree[now].l=l;tree[now].r=r;
if (l==r)
{
tree[now].tot=a[l];
return;
}
int mid=(l+r)>>1;
tree[now].ls=treesize+1;
buildtree(l,mid);
tree[now].rs=treesize+1;
buildtree(mid+1,r);
update(now);
}
inline void addition(int k,int l,int r,int dat)
{
downput(k);
int x=tree[k].l,y=tree[k].r;
if (l==x&&r==y)
{
tree[k].add+=dat;
tree[k].tot+=dat*(y-x+1);
return;
}
int mid=(x+y)>>1;
if (r<=mid) addition(tree[k].ls,l,r,dat);
else if (l>mid) addition(tree[k].rs,l,r,dat);
else
{
addition(tree[k].ls,l,mid,dat);
addition(tree[k].rs,mid+1,r,dat);
}
update(k);
}
inline void ask(int k,int l,int r)
{
int x=tree[k].l,y=tree[k].r;
if (l==x&&r==y) {ans+=(long long)tree[k].tot;return;}
if (tree[k].add)downput(k);
int mid=(x+y)>>1;
if (r<=mid) ask(tree[k].ls,l,r);
else if (l>mid) ask(tree[k].rs,l,r);
else
{
ask(tree[k].ls,l,mid);
ask(tree[k].rs,mid+1,r);
}
update(k);
}
int main()
{
n=read();
for (int i=1;i<=n;i++)a[i]=read();
buildtree(1,n);
m=read();
for (int i=1;i<=m;i++)
{
int opr=read(),x,y,z;
if(opr==1)
{
x=read();y=read();z=read();
addition(1,x,y,z);
}else
if (opr==2)
{
x=read(),y=read();
ans=0;
ask(1,x,y);
printf("%lld\n",ans);
}
}
}