wikioi1082【线段树练习 3 】

题目描述 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);

		}

	}

}

巴特西

wikioi1082【线段树练习 3 】

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

最新文章

热门文章