比赛 |
数列操作练习题 |
评测结果 |
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);
}