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