| 记录编号 |
142282 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
数列操作C |
最终得分 |
100 |
| 用户昵称 |
 wolf. |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.570 s |
| 提交时间 |
2014-12-07 01:31:25 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
ofstream nnew("shuliec.in",ios::app);
ifstream fin("shuliec.in");
#define fout cout
#else
ifstream fin("shuliec.in");
ofstream fout("shuliec.out");
#endif
/////////////////////////////////线段树
class leaf{
public:
int left;
int right;
int up;
long long add;
long long n;
leaf(){
left=0;//该点区间[left,right]
right=0;
add=0;// ADD命令产生的值
up=0;// 表示"该区间每个值都应加上该 up "用于向下求和时用 加快运行速度 根据需要利用区间大小计算
n=0;//起始时该节点所控制范围的和 初始化后不修改该值
}
};
vector<leaf> tree;//保存所有节点
vector<int> sign;//保存叶子节点在树中的下标，加快从叶子节点初始化的速度
void _build(int p,int l,int r){//构造线段树
tree[p].left=l;//确立区间范围
tree[p].right=r;
if(l>=r){// true时为叶子
sign[l]=p;//标记叶子节点的下标
return;
}
_build(p*2,l,(l+r)/2);//递归创建树
_build(p*2+1,(l+r)/2+1,r);//2*p与2*p+1为儿子
}
void _refresh_up(int p,int v){//由叶子节点向上更新
tree[p].n+=v;
if(p==1){//根
return;
}
_refresh_up(p/2,v);//找爸爸
}
long long _sum(int p,int l,int r){
if(tree[p].right==r&&tree[p].left==l){//该节点恰好为所修改的范围
return tree[p].n+tree[p].add+(tree[p].right-tree[p].left+1)*tree[p].up;//将该区间原始的数、新的数、未加的数求和返回
}
int mid=(tree[p].left+tree[p].right)/2;
tree[2*p].up+=tree[p].up;//将up拆给儿子
tree[2*p+1].up+=tree[p].up;
tree[p].add+=(tree[p].right-tree[p].left+1)*tree[p].up;//应将up转化为add储存
tree[p].up=0;//删除分解过了的up
if(r<=mid){//二分向下 不解释
return _sum(2*p,l,r);//递归--->逐级返回
}else if(l>mid){
return _sum(2*p+1,l,r);
}else{
return _sum(2*p+1,mid+1,r)+_sum(2*p,l,mid);
}
}
void _add(int p,int l,int r,int v){
int mid=(tree[p].left+tree[p].right)/2;
if(tree[p].right==r&&tree[p].left==l){//该节点恰好为所修改的范围
tree[p].up+=v;//给该节点记录一下即可
return;
}
tree[p].add+=(r-l+1)*v;//将up=v转化
if(r<=mid){//二分向下
_add(2*p,l,r,v);
}else if(l>mid){
_add(2*p+1,l,r,v);
}else{
_add(2*p,l,mid,v);
_add(2*p+1,mid+1,r,v);
}
}
///////////////////////////树状数组
vector<long long> TT[3];
int lowbit(int n){//基础不解释
return n&(-n);
}
long long _ssum(int cmd,int p,int l,int r){//一个函数干三个活
if(cmd==2){//最扯最抽象的部分
long long sum=0,left=0,right=0;
sum+=_ssum(0,r,0,0)-_ssum(0,l-1,0,0);
right+=(r+1)*_ssum(1,r,0,0);
for(int i=r;i>0;i-=lowbit(i)){
right-=TT[2][i];
}
left+=l*_ssum(1,l-1,0,0);
for(int i=l-1;i>0;i-=lowbit(i)){
left-=TT[2][i];
}
return sum+(right-left);
}
if(cmd==1){//差分前N项和
long long sum=0;
for(int i=p;i>0;i-=lowbit(i)){
sum+=TT[1][i];
}
return sum;
}
if(cmd==0){//原数列前N项和
long long sum=0;
for(int i=p;i>0;i-=lowbit(i)){
sum+=TT[0][i];
}
return sum;
}
}
void _aadd(bool cmd,int p,int l,int r,int n){//一个函数两项任务
if(!cmd){//在原数列中添加一值
for(int i=p;i<TT[0].size();i+=lowbit(i)){
TT[0][i]+=n;
}
return;
}
if(cmd){//在差分数列中添加一个值
for(int i=l;i<TT[0].size();i+=lowbit(i)){
TT[1][i]+=n;
}
for(int i=r+1;i<TT[0].size();i+=lowbit(i)){
TT[1][i]-=n;
}
int e;
e=n*l;
for(int i=l;i<TT[0].size();i+=lowbit(i)){
TT[2][i]+=e;
}
e=n*(r+1);
for(int i=r+1;i<TT[0].size();i+=lowbit(i)){
TT[2][i]-=e;
}
}
}
///////////////////////////
int main(){
srand(time(0));
if(rand()%2){//线段树
int n;
fin>>n;
sign.resize(n+1,0);//确定长度
int l=n*log((double)n)/log(2.0);//确定长度
tree.resize(l);//确定长度 省空间
_build(1,1,n);//创建线段树
for(int i=1;i<=n;++i){
int e;
fin>>e;
_refresh_up(sign[i],e);//从叶子节点向上更新
}
int t;
fin>>t;
const string A="ADD";
for(int i=0;i!=t;++i){//如题
string txt;
fin>>txt;
if(txt==A){
int l,r,n;
fin>>l>>r>>n;
_add(1,l,r,n);
}else{
int a,b;
fin>>a>>b;
fout<<_sum(1,a,b)<<endl;
}
}
}else{//树状数组
int n;
fin>>n;
TT[0].resize(n+1,0);//vector就是这么用的
TT[1].resize(n+1,0);//我就是不喜欢直接写具体长度
TT[2].resize(n+1,0);//你咬我
for(int i=0;i!=n;++i){
int e;
fin>>e;
_aadd(0,i+1,0,0,e);//添加原始数据 第三四个0无意义 只是为了配合函数形式
}
int N;
fin>>N;
const string A="ADD";
for(int i=0;i!=N;++i){//如题
string txt;
fin>>txt;
if(txt==A){//add
int l,r,e;
fin>>l>>r>>e;
_aadd(1,0,l,r,e);
}else{//sum
int l,r;
fin>>l>>r;
fout<<_ssum(2,0,l,r)<<endl;
}
}
}
//-------------------------*/
#if defined wolf
cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
#endif
return 0;
}
//Designed by wolf
//Sat Nov 22 2014