比赛 数列操作练习题 评测结果 AAAAAAAAA
题目名称 数列操作B 最终得分 100
用户昵称 祖国栋梁 运行时间 0.112 s
代码语言 C++ 内存使用 3.75 MiB
提交时间 2017-03-19 08:32:45
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<iostream>
#define MAXN 100001
//----------------------------------------------------
void build(int l,int r,int rt);
void pushdown(int rt,int l,int r);
void pushup(int rt);
void query(int l,int r,int rt,int i);
void update(int l,int r,int rt,int L,int R,int v);
//----------------------------------------------------
long int a[MAXN],lazy[4*MAXN],zhui[4*MAXN];
int main()
{
	freopen("shulieb.in","r",stdin);
	freopen("shulieb.out","w",stdout);
	using namespace std;
	long int n,m;
	scanf("%ld",&n);
	if(n==0)
		return 0; 
	for(int i=1;i<=n;i++)
		scanf("%ld",&a[i]);
	scanf("%ld",&m);
	char st[23];
	build(1,n,1);
	for(int i=0;i<m;i++)	
	{
		scanf("%s",&st);
		if(st[0]=='Q')
		{
			int i;
			scanf("%d",&i);
			query(1,n,1,i);
		}
		else
		{
			int i,j,v;
			scanf("%d%d%d",&i,&j,&v);
			update(1,n,1,i,j,v);
		}
	}
	return 0;
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		zhui[rt]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void pushdown(int rt,int l,int r)
{
	if(lazy[rt]!=0)
	{
		int mid=l+r>>1;
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		zhui[rt<<1]+=(lazy[rt]*(mid-l+1));
		zhui[rt<<1|1]+=(lazy[rt]*(r-mid));
		lazy[rt]=0;
	}
}
void update(int l,int r,int rt,int L,int R,int v)
{
	if(L<=l&&R>=r)
	{
		lazy[rt]+=v;
		zhui[rt]+=((r-l+1)*v);
		return;
		}
		pushdown(rt,l,r);
		int mid=l+r>>1;
		if(L<=mid) update(l, mid, rt<<1, L,R,v);
		if(mid<R) update(mid+1, r, rt<<1|1, L,R,v);
		pushup(rt);
}
void pushup(int rt)
{
	zhui[rt]=zhui[rt<<1]+zhui[rt<<1|1]; 
}
void query(int l,int r,int rt,int i)
{
	if(l==r)
	{
		printf("%ld\n",zhui[rt]);
		return;
	}
	pushdown(rt,l,r);
	int mid=l+r>>1;
	if(i<=mid)
	query(l,mid,rt<<1,i);
	else
	query(mid+1,r,rt<<1|1,i);
}