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