比赛 |
数列操作练习题 |
评测结果 |
AAAAAAAAAA |
题目名称 |
数列操作C |
最终得分 |
100 |
用户昵称 |
_Itachi |
运行时间 |
0.340 s |
代码语言 |
C++ |
内存使用 |
4.87 MiB |
提交时间 |
2017-03-18 19:05:12 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define ls(x) ch[(x)][0]
#define rs(x) ch[(x)][1]
const int maxn=100005;
int n,m,RT=0,cnt=0,ch[maxn][2],size[maxn],fa[maxn];
LL a[maxn],b[maxn],v[maxn],lazy[maxn];
void up(int x){
size[x]=size[ls(x)]+size[rs(x)]+1;
v[x]=v[ls(x)]+v[rs(x)]+a[x];
}
void down(int x){
if(!x||!lazy[x])return;
lazy[ls(x)]+=lazy[x],lazy[rs(x)]+=lazy[x];
v[ls(x)]+=lazy[x]*size[ls(x)],v[rs(x)]+=lazy[x]*size[rs(x)];
a[ls(x)]+=lazy[x],a[rs(x)]+=lazy[x];
lazy[x]=0;
}
void turn(int x){
int y=fa[x],z=fa[y];bool b=ch[y][1]==x;
fa[ch[y][b]=ch[x][!b]]=y,
fa[ch[x][!b]=y]=x,fa[x]=z;
ch[z][ch[z][1]==y]=x;
up(y),up(x);
}
void dig(int x,int tp){
down(x);
for(int y,z;fa[x]^tp;turn(x)){
y=fa[x],z=fa[y];
down(z),down(y),down(x);
if(z^tp)
if((ls(y)==x)==(ls(z)==y))turn(y);
else turn(x);
}
if(!tp)RT=x;
}
int set(int l,int r,int Fa){
if(l>r)return 0;
int x=++cnt,mid=(l+r)>>1;
fa[x]=Fa,a[x]=b[mid],size[x]=1;
ls(x)=set(l,mid-1,x),rs(x)=set(mid+1,r,x);
up(x);return x;
}
int find(int th){
int x=RT;th++;
while(true){
if(size[ls(x)]+1==th)return x;
if(size[ls(x)]+1< th)th-=size[ls(x)]+1,x=rs(x);
else x=ls(x);
}
}
void add(int l,int r,LL x){
dig(find(l-1),0),dig(find(r+1),RT);
int son=ls(rs(RT));
lazy[son]+=x,v[son]+=size[son]*x,a[son]+=x;
}
LL get(int l,int r){
dig(find(l-1),0),dig(find(r+1),RT);
return v[ls(rs(RT))];
}
int main(){
freopen("shuliec.in","r",stdin);freopen("shuliec.out","w",stdout);
scanf("%d",&n);int i,s,t;LL x;char o[10];
for(i=1;i<=n;i++)scanf("%lld",&b[i]);
RT=set(0,n+1,0);scanf("%d",&m);
while(m--){
scanf("%s%d%d",o,&s,&t);
if(o[0]=='S')printf("%lld\n",get(s,t));
else scanf("%lld",&x),add(s,t,x);
}
}