比赛 数列操作练习题 评测结果 AAAAAAAAAA
题目名称 数列操作C 最终得分 100
用户昵称 rvalue 运行时间 0.111 s
代码语言 C++ 内存使用 12.50 MiB
提交时间 2017-03-18 19:52:08
显示代码纯文本
#include <cstdio>
using namespace std;

const int MAXN=100010;
typedef long long LL;

struct Node{
	int start;
	int terminal;
	long long sum;
	long long add;
	Node* lch;
	Node* rch;
};

Node N[MAXN<<2];
Node* top;

int n;
int m;

void Build(Node*,int,int);
void Add(Node*,int,int,LL);
void PushDown(Node*);
long long Query(Node*,int,int);
void FastRead(int&);
void FastRead(long long &);

int Main(){
#ifndef ASC_LOCAL
	freopen("shuliec.in","r",stdin);
	freopen("shuliec.out","w",stdout);
#endif
	int start,terminal;
	long long d;
	char buf[10];
	top=N;
	FastRead(n);
	Build(N,1,n+1);
	FastRead(m);
	//printf("N->start:%d N->terminal:%d\n",N->start,N->terminal);
	//Query(N,1,n+1);
	while(m--){
		scanf("%s",buf);
		if(*buf=='A'){
			FastRead(start);
			FastRead(terminal);
			FastRead(d);
			Add(N,start,terminal+1,d);
		}
		if(*buf=='S'){
			FastRead(start);
			FastRead(terminal);
			printf("%lld\n",Query(N,start,terminal+1));
		}
	}
	return 0;
}

void Build(Node* root,int start,int terminal){
	root->start=start;
	root->terminal=terminal;
	if(terminal-start==1){
		FastRead(root->sum);
		return;
	}
	int mid=(start+terminal)>>1;
	Build(root->lch=++top,start,mid);
	Build(root->rch=++top,mid,terminal);
	root->sum=root->lch->sum+root->rch->sum;
}

long long Query(Node* root,int start,int terminal){
	//printf("root->:sum=%lld start=%d terminal=%d ,root-N=%d\n",root->sum,root->start,root->terminal,root-N);
	if(start<=root->start&&root->terminal<=terminal){
		return root->sum;
	}
	if(root->add!=0)
		PushDown(root);
	if(terminal<=root->lch->terminal)
		return Query(root->lch,start,terminal);
	if(start>=root->rch->start)
		return Query(root->rch,start,terminal);
	return Query(root->lch,start,terminal)+Query(root->rch,start,terminal);
}

void Add(Node* root,int start,int terminal,long long x){
	//printf("root->:sum=%lld start=%d terminal=%d ,root-N=%d\n",root->sum,root->start,root->terminal,root-N);
	if(start<=root->start&&root->terminal<=terminal){
		root->sum+=x*(root->terminal-root->start);
		root->add+=x;
		return;
	}
	if(root->add!=0)
		PushDown(root);
	if(start<root->lch->terminal)
		Add(root->lch,start,terminal,x);
	if(terminal>root->rch->start)
		Add(root->rch,start,terminal,x);
	root->sum=root->lch->sum+root->rch->sum;
}

inline void PushDown(Node* root){
	root->lch->add+=root->add;
	root->rch->add+=root->add;
	root->lch->sum+=root->add*(root->lch->terminal-root->lch->start);
	root->rch->sum+=root->add*(root->rch->terminal-root->rch->start);
	root->add=0;
}

void FastRead(int& target){
	bool flag=false;
	target=0;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-'){
			flag=true;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-'0';
		ch=getchar();
	}
	if(flag)
		target=-target;
}

void FastRead(long long& target){
	bool flag=false;
	target=0;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-'){
			flag=true;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-'0';
		ch=getchar();
	}
	if(flag)
		target=-target;
}

int WORKING=Main();
int main(){;}